Two Pinters

Algorithms
topic
Catalogue
  1. 1. Same Direction
    1. 1.1. 27. Remove Element
    2. 1.2. 26. Remove Duplicates from Sorted Array
    3. 1.3. 80. Remove Duplicates from Sorted Array II
  2. 2. Two Sequence
    1. 2.1. 88. Merge Sorted Array

Same Direction

27. Remove Element

  • left pointer represents the postion that next valid result will be put in!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    # Time : O(n), Sapce : O(1)
    class Solution(object):
        def removeElement(self, nums, val):
            left = 0
            for i in range(len(nums)):
                if nums[i] != val:
                    nums[left] = nums[i]
                    left += 1
            return left

26. Remove Duplicates from Sorted Array

  • first pointer represents the last position in the result!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # Time : O(n), Sapce : O(1)
    class Solution(object):
        def removeDuplicates(self, nums):
            if not nums:
                return 0

            first = 0
            for i in range(1, len(nums)):
                if nums[i] != nums[first]:
                    first += 1
                    nums[first] = nums[i]
            return first+1

80. Remove Duplicates from Sorted Array II

  • small trick: 1. start interation from index 2, 2. comprare with the element with only the second last element!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # Time : O(n), Sapce : O(1)
    class Solution(object):
        def removeDuplicates(self, nums):
            n = len(nums)
            if n <= 2:
                return n

            first = 1
            for i in range(2, n):
                if nums[i] != nums[first-1]:
                    first += 1
                    nums[first] = nums[i]
            return first + 1

Two Sequence

88. Merge Sorted Array

  • two pointers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def merge(self, nums1, m, nums2, n):
        p1, p2 = m - 1, n - 1
        p = m + n - 1
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            p -= 1

        while p2 >= 0:
            nums1[p] = nums2[p2]
            p -= 1
            p2 -= 1
Share