Left Right Heads

Classic

125. Valid Palindrome (Easy)

Solution

  • Move left until it points to an alphanumeric

  • Once left points to an alphanumeric, move right until it points to an alphanumeric.

  • When both points to an alphanumeric, check if both are equal, if not return False. And advance both left and right pointers.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the string

Space Complexity: O(1)

def isPalindrome(self, s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

Reverse a subarray

Generic - Reverse of subarray

Problem

Given an array of object (can be string, integer), reverse the subarray of the array with given left and right pointers (both inclusive) and must do it in-place.

Solution

This is a classical two pointers solution.

Both left and right pointers are already given in the problem statement. Both pointers start from opposite directions and move towards each other. They stop when they meet each other, which is at the center of them.

While moving the both pointers towards each other, we need to swap the elements between two pointers.

Analysis

Time Complexity: O(k)

where:

  • k is the length of the subarray

for k/2 swaps

Space Complexity: O(1)

def reverseSubArray(arr, left, right):  # right is inclusive
    while left < right:
        tmp = arr[right]
        arr[right] = arr[left]
        arr[left] = tmp
        left += 1
        right -= 1

344. Reverse String (Easy)

Also

Solution

A special case of Reverse a subarray, where the subarray is the array itself. Which means, the left and right pointers are 0 and len(arr) - 1 respectively.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the string

for N/2 swaps

Space Complexity: O(1)

def reverseString(self, s: List[str]) -> None:
    reverseSubArray(s, 0, len(s) - 1)  # inplace

541. Reverse String II (Easy)

Solution

Must reverse first k characters in every 2 * k characters.

Also, if there are fewer than k characters left, reverse all of them. To handle this situation, we can get the min(i + k - 1, n - 1). If the i + k - 1 is overflowing, then the minimum would be the n - 1.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the string

Space Complexity: O(N)

to manipulate string as an array.

def reverseStr(self, s: str, k: int) -> str:
    n = len(s)
    s = list(s)
    for i in range(0, n, 2 * k):
        reverseSubArray(s, i, min(i + k - 1, n - 1))
    return "".join(s)

2000. Reverse Prefix of Word (Easy)

Solution

Two subproblems:

  • Find the index of first occurrence of ch, and let this index be right.

  • Reverse the subarray from 0 to right.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the string

Space Complexity: O(N)

to manipulate string as an array.

def reversePrefix(self, word: str, ch: str) -> str:
    n = len(word)
    word = list(word)
    for right in range(n):
        if word[right] == ch:
            reverseSubArray(word, 0, right)
            break
    return "".join(word)

151. Reverse Words in a String (Medium)

Solution

Two main Subproblems:

  • Strip redundant whitespaces

  • Reverse words * Reverse entire string * Reverse each (reversed word) (Words are separated by a single whitespace)

While reversing reversed word in the loop, we need to exclude right because it points to " ", hence right - 1 is used. When the for loop ends, the last word wouldn’t be reversed, hence we need to reverse the last word too. But here, right is already stopped at n - 1 , we don’t need to use right - 1.

And when updating left, since right is already pointing to a whitespace, left must be updated to right + 1.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the string

Space Complexity: O(N)

to manipulate string as an array.

def reverseWords(self, s: str) -> str:
    s = " ".join(s.split())  # cleans all the redundant whitespaces
    n = len(s)
    s = list(s)
    reverseSubArray(s, 0, n - 1)  # reverse entire array
    left = 0
    for right in range(n):
        if s[right] == " ":
            reverseSubArray(s, left, right - 1)
            left = right + 1
    reverseSubArray(s, left, right)
    return "".join(s)

186. Reverse Words in a String II (Medium)

Solution

This is actually the second subproblem mentioned for 151. Reverse Words in a String (Medium).

Here we don’t need to trim the whitespaces. Also, the input s is not string, instead its an array.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

def reverseWords(self, s: List[str]) -> None:
    n = len(s)
    reverseSubArray(s, 0, n - 1)
    left = 0
    for right in range(n):
        if s[right] == " ":
            reverseSubArray(s, left, right - 1)
            left = right + 1
    reverseSubArray(s, left, right)

557. Reverse Words in a String III (Easy)

Solution

Intention: Reverse all characters of each word, keeping whitespaces intact.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the string

Space Complexity: O(N)

to manipulate string as an array.

def reverseWords(self, s: str) -> str:
    n = len(s)
    s = list(s)
    left = 0
    for right in range(n):
        if s[right] == " ":
            reverseSubArray(s, left, right - 1)
            left = right + 1
    reverseSubArray(s, left, right)
    return "".join(s)

Reverse Individual Elements

345. Reverse Vowels of a String (Easy)

Solution

  • Move left until it points to a vowel

  • Once left points to a vowel, move right until it points to a vowel.

  • When both points to a vowel, swap it. And advance both left and right pointers.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the string

Space Complexity: O(N)

to manipulate string as an array.

def reverseVowels(self, s: str) -> str:
    left, right = 0, len(s) - 1
    s = list(s)
    vowels = set("aeiouAEIOU")
    while left < right:
        if s[left] not in vowels:
            left += 1
        elif s[right] not in vowels:
            right -= 1
        else:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
    return "".join(s)

917. Reverse Only Letters (Easy)

Solution

  • Move left until it points to a English alphabets

  • Once left points to a vowel, move right until it points to a English alphabets.

  • When both points to a vowel, swap it. And advance both left and right pointers.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the string

Space Complexity: O(N)

to manipulate string as an array.

def reverseOnlyLetters(self, s: str) -> str:
    left, right = 0, len(s) - 1
    s = list(s)
    while left < right:
        if not s[left].isalpha():
            left += 1
        elif not s[right].isalpha():
            right -= 1
        else:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
    return "".join(s)

Rotate - Using Reverse

189. Rotate Array (Medium)

Also

Solution

Essentially this is right rotation.

This approach is based on the fact that when we rotate the array k times, k elements from the back end of the array come to the front and the rest of the elements from the front shift backwards.

In this approach, we firstly reverse all the elements of the array. Then, reversing the first k elements followed by reversing the rest n - k elements gives us the required result.

Let n = 7 and k = 3.

Original List                   : 1 2 3 4 5 6 7

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

def rotate(self, nums: List[int], k: int) -> None:
    n = len(nums)
    k = k % n
    reverseSubArray(nums, 0, n - 1)
    reverseSubArray(nums, 0, k - 1)
    reverseSubArray(nums, k, n - 1)

Quick Left Rotation (Basic)

Solution

Essentially this is left rotation.

Similar to 189. Rotate Array (Medium)

Let n = 7 and k = 2.

Original List                     : 1 2 3 4 5 6 7

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

def leftRotate(self, nums, k, n):
    n = len(nums)
    k = k % n
    reverseSubArray(nums, 0, n - 1)
    reverseSubArray(nums, 0, n - k - 1)
    reverseSubArray(nums, n - k, n - 1)

Sorted Array

167. Two Sum II - Input Array Is Sorted (Medium)

Also

Solution

Dry Run

Consider number = [1, 2, 4, 6, 7] and target = 6. Also left and right starts from opposite ends, that is 0 and n - 1 respectively.

Addition of both pointed elements is 1 + 7 which is greater than target 6. Which means, we need to move the right pointer because right to right pointer will always point to greater element and the addition would be still greater, hence moving right pointer to the left right -= 1) makes sense which will decrease the total.

Now, left points to 1 and right to 6. Addition would be 7, again move right pointer.

Now left points to 1 and right to 4. Addition would be 5, which is less than the target. Now we need to move left pointer, since only then we have a possibility of increasing the addition to reach target.

Now, left points to 2 and right to 4. Addition would be 6 which is also the target, hence return the indices (unity representation).

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

def twoSum(self, numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total < target:
            left += 1
        elif total > target:
            right -= 1
        else:
            return [left + 1, right + 1]
    return [-1, -1]

Sort The Array

977. Squares of a Sorted Array (Easy)

Also

Solution

The maximum of whole number would be the maximum of square of minimum and square of maximum. This is the logic for this problem. This can be for any subarray in the array.

So, we have to fill the elements to ans incrementally from the last index, since we are finding maximum element in each step.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

Assuming the returning array ans is not considered as auxiliary space.

def sortedSquares(self, nums: List[int]) -> List[int]:
    left, right = 0, len(nums) - 1
    ans = []
    square = lambda i: nums[i] * nums[i]
    while left <= right:
        if square(right) > square(left):
            ans.insert(0, square(right))
            right -= 1
        else:
            ans.insert(0, square(left))
            left += 1
    return ans

905. Sort Array By Parity (Easy)

Solution

  • Move left until it points to a even number.

  • Once left points to a even number, move right until it points to a odd number.

  • Swap the numbers. And advance both left and right pointers.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

Assuming the returning array ans is not considered as auxiliary space.

def sortArrayByParity(self, nums: List[int]) -> List[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        if nums[left] % 2 == 0:
            left += 1
        elif nums[right] % 2 == 1:
            right -= 1
        else:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
    return nums