LeetCode (Algorithms#15) ‒ 3Sum

Problem

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Example:

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

The problem is a direct extension of2Sum, which runs in $O(n)$. With 3Sum, it should be reasonable to assume that a $O(n^2)$ solution is possible. The trick is in handling repeated combinations of the same three numbers, which I initially tried using a hashset of solutions, with a sum of each number's hash to hash to a solution. This worked, but was too slow for one of the tests.

The better approach is to first sort the array, and then while considering each of the $n$ numbers, use a left and right pointer, and while moving them inward, solve the 2Sums problem with a target of $-n$. To iterate the left and right pointers, we chose to increase the left pointer if the sum is less than 0, and decrease the right pointer if the sum is greater than the 0. Since the array is sorted, increasing or decreasing either pointer will change the sum to the next lowest or highest value, respectively, ensuring that no solution is skipped. We can simultaneously skip over any numbers on both the left and right side that are repeats to ensure only a new solution is considered. The code below implements this approach.

Time complexity: $O(n^2)$
Space complexity: $O(n^2)$
Runtime: 82 ms (77.86%)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> sums = new ArrayList<List<Integer>>(); if (nums==null || nums.length < 3) return sums; Arrays.sort(nums); int l, r, v, len = nums.length; List<Integer> L; for (int i=0; i<len-1; i++) { if (i>0 && nums[i-1]==nums[i]) continue; l = i+1; r = len-1; while (l < r) { v = nums[i]+nums[l]+nums[r]; if (v < 0) l++; else if (v > 0) r--; else { // sum == 0 L = new ArrayList<Integer>(3); L.add(nums[i]); L.add(nums[l]); L.add(nums[r]); sums.add(L); v=nums[l++]; while (l<r && nums[l]==v) l++; v=nums[r--]; while (r>l && nums[r]==v) r--; } } } return sums; }

LeetCode (Algorithms#14) ‒ Longest Common Prefix

Problem

Write a function to find the longest common prefix string amongst an array of strings.

Solution

For a set of $n$ strings, the brute force solution is sufficient as you must compare a character in each string to determine if it belongs to a common prefix. Thus, the optimal solution is $O(n^2)$, where the worst case is all strings match.

Time complexity: $O(n^2)$
Space complexity: $O(n^2)$
Runtime: 12ms (52.13%)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public String longestCommonPrefix(String[] strs) { if (strs.length==0 || strs[0].length()==0) return ""; else if (strs.length==1) return strs[0]; StringBuilder sb = new StringBuilder(); int j = 0; char prefChar; boolean isPrefChar; while (j<strs[0].length()) { prefChar = strs[0].charAt(j); isPrefChar = true; for (int i=1; i<strs.length; i++) isPrefChar &= j<strs[i].length() && strs[i].charAt(j)==prefChar; if (isPrefChar) sb.append(prefChar); else break; j++; } return sb.toString(); }