Two pointers

LC 75 Sort Colors

By using two pointers, this problem can be solved.

• P0 is the explored right boundary of 0. P2 is the explored left boundary of 2.
• During the traversing process, if we meet with 0, swap with p0 and increase P0 by 1.
• If we meet with 2, swap with p2 and decrease p2 by 1

# Time complexity O(n)
# Space complexity: O(1)
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        p0, p2 = 0 , len(nums)-1
        for j in range(len(nums)-1, -1, -1):
            if nums[j]==2:
                p2 -= 1
            else:
                break
        for j in range(len(nums)):
            if nums[j]==0:
                p0 += 1
            else:
                break
        i = p0
        while p0 < p2 and i<=p2:
            if nums[i]==2:
                nums[i], nums[p2] = nums[p2], nums[i]
                p2 -= 1
            elif nums[i]==0:
                nums[i], nums[p0] = nums[p0], nums[i]
                p0 += 1
                if i==p0-1:
                    i += 1
            else: # nums[i]==1
                i += 1

Based on this article, it is a Dutch national flag problem. Rewrite the code in a more concise way:

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        def swap(i, j):nums[i], nums[j] = nums[j], nums[i]
        p0, p1, p2 = 0, 0, len(nums)-1
        while p0<p2 and p1<=p2:
            if nums[p1] == 0:
                if p0==p1:p1 += 1
                else:swap(p0, p1)
                p0 += 1
            elif nums[p1] == 1:
                p1 += 1
            else:
                swap(p1, p2)
                p2 -= 1

16. 3Sum Closest

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = sum(nums[:3])
        for i in range(len(nums)):
            l, r = i+1, len(nums)-1
            while l<r:
                this_res = nums[i] + nums[l] + nums[r]
                if this_res==target:
                    return target
                if abs(this_res - target) < abs(res-target):
                    res = this_res
                if this_res < target:
                    l += 1
                if this_res > target:
                    r -= 1
        return res