DenCT/test-storage / DSA Notes /Two Pointers.md
DenCT's picture
|
download
raw
9.23 kB
metadata
tags:
  - notes
  - two-pointers

Valid Palindrome EASY

Given a string s, return true if it is a palindrome, otherwise return false. A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.

Input: s = "Was it a car or a cat I saw?"
Output: true
Explanation: After considering only alphanumerical characters we have 
"wasitacaroracatisaw", which is a palindrome.

Input: s = "tab a cat"
Output: false
Explanation: "tabacat" is not a palindrome.

Solution

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

To determine if a given string is a valid palindrome, we can use two pointers approach. We initialize two pointers, one at the beginning of the string (left) and the other at the end of the string (right). We then compare characters at these two pointers. If they are both alphanumeric characters and equal in value (ignoring case), we move both pointers towards the centre of the string. If they are not equal, we know the string is not a palindrome. We continue this process until the two pointers meet or cross each other.

  1. Start with two pointers, one at the start other at the end of string, and start moving both towards each other.
  2. if any of the characters at l or r is not alphanumeric, the pointer is moved forward or backward.
  3. If the character at l and r are not same when they are lowercase, False is returned, else the pointers are moved forward and backward.
  4. At the end, True is returned, indicating the string is palindrome.

Two Sum II MEDIUM

Given an array of integers numbers that is sorted in non-decreasing order. Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice. There will always be exactly one valid solution. Your solution must use O(1)O(1) additional space.

Input: numbers = [1,2,3,4], target = 3
Output: [1,2]

Explanation:
The sum of 1 and 2 is 3. Since we are assuming a 1-indexed array, index1 = 1, 
index2 = 2. We return [1, 2].

[!info] Time & Space Complexity You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Solution

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            two_sum = numbers[l] + numbers[r]
            if two_sum < target:
                l += 1
            elif two_sum > target:
                r -= 1
            else:
                return [l + 1, r + 1]
  1. Start with two pointers, l and r , one in the starting of string and other at the end.
  2. Calculate the sum of the numbers that are in the l and r pointers. If the sum is lesser than target, move l forward and if sum is greater than target, move r backward.
  3. If both cases fail, we have our answer, which is [l+1, r+1] . Return it.

3 Sum MEDIUM

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct. The output should not contain any duplicate triplets. You may return the output and the triplets in any order.

**Example 1:**
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

**Explanation:**
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].

**Example 3**:
Input: nums = [0,0,0]
Output: [[0,0,0]]

**Explanation**: The only possible triplet sums up to 0.

Solution

To find all unique triplets that sum to zero, we can use a three-pointer approach. First, we sort the input array nums in non-decreasing order. Then, we iterate through the array with a fixed first element (i). For each fixed first element, we use two pointers (left and right) to find the other two elements that sum to the negation of the fixed first element. As the array is sorted, we can move these two pointers towards each other to efficiently find all possible triplets.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        size = len(nums)
        nums.sort()
        for i in range(size - 2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            l, r = i + 1, size - 1
            while l < r:
                three_sum = nums[i] + nums[l] + nums[r]
                if three_sum < 0:
                    l += 1
                elif three_sum > 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
        return res

[!info] Time and Space complexity You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Container with most water MEDIUM

You are given an integer array heights where heights[i] represents the height of the ith ith bar. You may choose any two bars to form a container. Return the maximum amount of water a container can store. ![[container-with-most-water.png.png]]

Example 1:
Input: height = [1,7,2,5,4,7,3,6]
Output: 36

Solution

To find the maximum area of water that can be held between two vertical lines, we can use a two-pointer approach. We initialize two pointers, one at the beginning of the input array (left) and the other at the end of the array (right). The area between the two vertical lines is calculated as the minimum of the heights at the two pointers multiplied by the distance between them. We then update the maximum area found so far and move the pointer with the smaller height towards the other pointer. We continue this process until the two pointers meet or cross each other.

class Solution:
    def maxArea(self, heights: List[int]) -> int:
        size = len(heights)
        l, r = 0, size - 1
        max_vol = 0
        while l < r:
            height = min(heights[l], heights[r])
            max_vol = max(max_vol, height * (r - l))
            if heights[l] <= heights[r]:
                l += 1
            else:
                r -= 1
        return max_vol

[!info] Time and Space complexity You should aim for a solution withO(n) time and O(1) space, where n is the size of the input array.

Trapping Rain Water HARD

You are given an array non-negative integers height which represent an elevation map. Each value height[i] represents the height of a bar, which has a width of 1. Return the maximum area of water that can be trapped between the bars. Example 1: ![[trapping-rain-water.png.png]]

Input: height = [0,2,0,3,1,0,1,3,2,1]
Output: 9

Solution

To find the amount of trapped rainwater in the given elevation histogram represented by the input array 'height', we can use a two-pointer approach. We initialize two pointers, one at the beginning of the array (left) and the other at the end of the array (right). We also initialize two variables to keep track of the maximum left height and maximum right height seen so far. While the left pointer is less than the right pointer, we compare the height at the left and right pointers. If the height at the left pointer is less than or equal to the height at the right pointer, it means we can trap water between the left pointer and the maximum left height. Otherwise, we can trap water between the right pointer and the maximum right height. At each step, we update the trapped water amount and move the pointers and update the maximum heights accordingly.

[!info] Time and Space Complexity You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_left, max_right = 0, 0
        trapped_water = 0
        while left < right:
            if height[left] <= height[right]:
                if height[left] >= max_left:
                    max_left = height[left]
                else:
                    trapped_water += max_left - height[left]
                left += 1
            else:
                if height[right] >= max_right:
                    max_right = height[right]
                else:
                    trapped_water += max_right - height[right]
                right -= 1
        return trapped_water

PREVIOUS: [[Arrays and Hashing]] | NEXT: [[Sliding Window]]

Xet Storage Details

Size:
9.23 kB
·
Xet hash:
191ae1d7370d7958afc815880b7a2b1d8d6f4bfcee307e37a6b1a0ab63df5425

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.