[Leetcode] Two Pointers in Array

Posted on | In , , |

Two Pointers in One Array

15. 3Sum

Leetcode: https://leetcode.com/problems/3sum/

Note:

  1. Sort array (to conveniently jump over duplicates)
  2. Use i as the main pointer, l = i + 1, r = len(nums) - 1
  3. If current sum == 0: we need to move both l and r.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def threeSum(self, nums):
    nums.sort()
    l, r = 0, len(nums) - 1
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:
                l += 1
            elif s > 0:
                r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
                while l < r and nums[r] == nums[r + 1]:
                    r -= 1
    return res

16. 3Sum Closest

Leetcode: https://leetcode.com/problems/3sum-closest/

My binary search solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def threeSumClosest(self, nums, target):
    if not nums or len(nums) < 3:
        return 0
    nums.sort()
    i = 0
    j = i + 1
    res = float('inf')
    for i in range(len(nums) - 2):
        for j in range(i + 1, len(nums) - 1):
            tar = target - nums[i] - nums[j]
            index = bisect_left(nums, tar, j + 1, len(nums))
            if index < len(nums):
                if abs(res - target) > abs(nums[i] + nums[j] + nums[index] - target):
                    res = nums[i] + nums[j] + nums[index]
                if index > j + 1 and abs(res - target) > abs(nums[i] + nums[j] + nums[index - 1] - target):
                    res = nums[i] + nums[j] + nums[index - 1]
            else:
                if abs(res - target) > abs(nums[i] + nums[j] + nums[index - 1] - target):
                    res = nums[i] + nums[j] + nums[index - 1]
    return res

Two Pointers solution: (Same as the 3 sum problem)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def threeSumClosest(self, nums: List[int], target: int) -> int:
    nums.sort()
    res = float('inf')
    for i in range(len(nums) - 2):
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if abs(s - target) < abs(res - target):
                res = s
            if s > target:
                r -= 1
                while l < r and nums[r] == nums[r + 1]:
                    r -= 1
            elif s < target:
                l += 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
            else:
                return target
    return res

259. 3Sum Smaller

Leetcode: https://leetcode.com/problems/3sum-smaller/

Note:

  1. Doesn’t need to consider the duplicates problem.
  2. If sum of numbers at i, l, r is smaller than target, then the sum would also smaller than the target if r keeps moving to l. Thus cnt += r - l
1
2
3
4
5
6
7
8
9
10
11
12
13
def threeSumSmaller(self, nums: List[int], target: int) -> int:
    nums.sort()
    cnt = 0
    for i in range(len(nums) - 2):
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s >= target:
                r -= 1
            elif s < target:
                cnt += r - l
                l += 1
    return cnt

18. 4Sum

Leetcode: https://leetcode.com/problems/4sum/

My Backtracking solution(TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def fourSum(self, nums, target):
    nums.sort()
    visited = set()
    def backtrack(index, comb, num_left, tar, res):
        if num_left == 0 and tar == 0:
            if "".join(list(map(lambda x: str(x), comb))) not in visited:
                res.append(comb[::])
                visited.add("".join(list(map(lambda x: str(x), comb))))
            return
        elif num_left < 0 and tar != 0:
            return
        for i in range(index, len(nums)):
            comb.append(nums[i])
            backtrack(i + 1, comb, num_left - 1, tar - nums[i], res)
            comb.pop()
    res = []
    backtrack(0, [], 4, target, res)
    return res

Two Pointers solution:

Note:

  1. Should notice jumping over duplicate numbers
  2. Calculate 3 sum first then calculate 4 sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    res = []
    nums.sort()
    def threeSum(arr, tar):
        res = []
        for i in range(len(arr) - 2):
            if i > 0 and arr[i] == arr[i - 1]: # JUMP
                continue
            l, r = i + 1, len(arr) - 1
            while l < r:
                s = arr[i] + arr[l] + arr[r]
                if s < tar:
                    l += 1
                elif s > tar:
                    r -= 1
                else:
                    res.append([arr[i], arr[l], arr[r]])
                    l += 1
                    r -= 1
                    while l < r and arr[l] == arr[l - 1]: # JUMP
                        l += 1
                    while l < r and arr[r] == arr[r + 1]: # JUMP
                        r -= 1
        return res
    i = 0
    while i < len(nums) - 3:
        threeRes = threeSum(nums[i + 1:], target - nums[i])
        for r in threeRes:
            res.append([nums[i]] + r)
        i += 1
        while 0 < i < len(nums) - 3 and nums[i] == nums[i - 1]: # JUMP
            i += 1
    return res

454. 4Sum II

Leetcode: https://leetcode.com/problems/4sum-ii/

Actually it’s not a two-pointer problem.

Note:

  1. Count the number of sums of all the combinations in A and B.
  2. Calculate sums in C and D and see if there’s any match in counter[-c-d]
1
2
3
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
    count = collections.Counter([a + b for a in A for b in B])
    return sum([count[-c-d] for c in C for d in D])

923. 3Sum With Multiplicity

Leetcode: https://leetcode.com/problems/3sum-with-multiplicity/

Note:

  1. When s == target, we have two situations to consider:
    1). The left and right number are the same
    2). The left and right number are different
  2. When they are different, we need to count both left and right numbers and multiply them (Note that we need to use l + 1 < r rather than l < r to count all the numbers)
  3. When they are the same:
    1
    2
    3
    4
    C(n, m) = n! / (m!(n - m)!)
    n = X, m = 2
    C(X, 2) = X! / (2!(X - 2)!) = X(X - 1)(X - 2)! / (2! / (X - 2)!)
            = X (X - 1) / 2

Thus we do cnt += (r - l + 1) * (r - l) / 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def threeSumMulti(self, nums, target):
    cnt = 0
    MOD = 10 ** 9 + 7
    nums.sort()
    for i in range(len(nums) - 2):
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s > target:
                r -= 1
            elif s < target:
                l += 1
            else:
                if nums[l] != nums[r]:
                    left = right = 1
                    while l + 1 < r and nums[l] == nums[l + 1]: # l + 1 < r
                        l += 1
                        left += 1
                    while l + 1 < r and nums[r] == nums[r - 1]:
                        r -= 1
                        right += 1
                    cnt += left * right
                    l += 1
                    r -= 1
                else:
                    cnt += (r - l + 1) * (r - l) / 2
                    break
    return cnt % MOD

611. Valid Triangle Number

Leetcode: https://leetcode.com/problems/valid-triangle-number/

Note:

  1. When starting searching for the next round, we don’t need to reset r to j + 1, instead, we can directly start from where we stopped in the last round.
  2. Since all the edges are triangle edge, don’t forget about to check if nums[i] == 0
1
2
3
4
5
6
7
8
9
10
11
12
def triangleNumber(self, nums: List[int]) -> int:
    cnt = 0
    nums.sort()
    for i in range(len(nums) - 2):
        r = i + 2 # [1]
        for j in range(i + 1, len(nums) - 1):
            if nums[i] == 0: # [2]
                continue
            while r < len(nums) and nums[i] + nums[j] > nums[r]:
                r += 1
            cnt += r - j - 1
    return cnt

11. Container With Most Water

Leetcode: https://leetcode.com/problems/container-with-most-water/

  • The area is decided by the shortest border, we move whichever border shorter to the center
1
2
3
4
5
6
7
8
9
10
def maxArea(self, height: List[int]) -> int:
    l, r = 0, len(height) - 1
    area = 0
    while l < r:
        area = max(area, (r - l) * min(height[l], height[r]))
        if height[l] <= height[r]:
            l += 1
        else:
            r -= 1
    return area

Two array/list problem

88. Merge Sorted Array

Leetcode: https://leetcode.com/problems/merge-sorted-array/submissions/

Note

Remember to add what’s left in list B into list A.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        cur = m + n - 1
        a = m - 1
        b = n - 1
        
        while cur >= 0 and a >= 0 and b >= 0:
            if A[a] > B[b]:
                A[cur] = A[a]
                a -= 1
            else:
                A[cur] = B[b]
                b -= 1
            cur -= 1
        
        # Add missing elements from B
        A[:b + 1] = B[:b + 1]