Day 2 Two Pointers

[llama90]

Problems

• 977. Squares of a Sorted Array
• 189. Rotate Array

Two Pointers

Overview

The pointers refer to an array's indexes. By using pointers, we can process two elements per loop, instead of just one.

• Two pointers each starting from the beginning and the end until they both meet
• One pointer moves at a slow pace while the other pointer moves at a faster pace

Both of the above patterns can reduce the time and space complexity.

Example

• Sum Exists in an Array
• Rotate Array k Steps
• Middle Element in a LinkedList

Reference

• Java Two Pointer Tecnique

[llama90]

Naive Approach

189

• Complexity:
  • Time: $ O(n) + O(n) = O(n) $
    • $ O(n) $: Copy rotated elements to a new array
    • $ O(n) $: Copy rotated array elements to the origin array
  • Space: $ O(n) $
    • $ O(n) $: Temporal array to copy rotated element from origin array
• Result:
  • Runtime: 4 ms, faster than 10.05% of Java online submissions for Rotate Array.
  • Memory Usage: 64.8 MB, less than 15.52% of Java online submissions for Rotate Array

977

• Complexity:
  • Time: $ O(n) + O(n log n) = O(n log n) $
    • $ O(n) $: Compute the square of elements
    • $ O(n log n) $: Sort the element using Arrays.sort() method
  • Space: $ O(n) $
    • $ O(n) $: Store the square of elements
• Result
  • Runtime: 9 ms, faster than 19.74% of Java online submissions for Squares of a Sorted Array.
  • Memory Usage: 56.4 MB, less than 5.74% of Java online submissions for Squares of a Sorted Array.

[llama90]

Improvement

189

• Complexity:
  • Time: $ O(n) + O(n) = O(n) $
    • $ O(n) $: Copy rotated elements to a new array
    • $ O(n) $: Copy rotated array elements to the origin array
  • Space: $ O(1) $
    • $ O(1) $: Temporal variable to swap rotated element
• Result:
  • Runtime: 1 ms, faster than 80.02% of Java online submissions for Rotate Array.
  • Memory Usage: 64.5 MB, less than 41.81% of Java online submissions for Rotate Array.
• Follow up:
  • Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

977

• Complexity:
  • Time: $ O(n) $
    • $ O(n) $: Compare the square of elements and copy elements to an output array
  • Space: $ O(n) $
    • $ O(n) $: Store the square of elements
• Result:
  • Runtime: 2 ms, faster than 77.00% of Java online submissions for Squares of a Sorted Array.
  • Memory Usage: 55.5 MB, less than 55.99% of Java online submissions for Squares of a Sorted Array.
• Follow up:
  • Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?