Flashcards for "Two Pointer and Sliding Window"

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        nums.sort()
        res = []

        for i1, num1 in enumerate(nums):
            if i1==0 or nums[i1]!=nums[i1-1]:

                ## Two sum logic
                i2=i1+1
                i3=len(nums)-1

                while i2<i3:
                    curr_sum = num1 + nums[i2] + nums[i3]

                    if curr_sum==0:
                        res.append([nums[i1],nums[i2], nums[i3]])
                        i2+=1
                        i3-=1

                        while i2<i3 and nums[i2]==nums[i2-1]:
                            i2+=1
                        
                        while i2<i3 and nums[i3]==nums[i3+1]:
                            i3-=1

                    else: 
                        if curr_sum<0:
                            i2+=1
                        else:
                            i3-=1
            
        return res
                        

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        

        max_profit=0
        lowest_price=prices[0]
        for price in prices:
            max_profit=max(max_profit, (price-lowest_price))
            lowest_price=min(price, lowest_price)
        
        return max_profit

class Solution:
    def maxArea(self, height: List[int]) -> int:
        """
        Find the maximum area of water that can be contained by two lines 
        from the given list of heights. The algorithm uses a two-pointer approach
        to evaluate the area between pairs of lines from the outermost pair 
        moving inwards, ensuring the optimal solution is found.

        :param height: List of integers representing the heights of lines.
        :return: The maximum area of water that can be contained.
        """

        # Initialize pointers for the leftmost and rightmost lines.
        left, right = 0, len(height) - 1

        # Initialize the variable to store the maximum area found.
        max_area = 0

        # Continue until the two pointers meet.
        while left < right:
            # Calculate the height and width of the current container.
            current_height = min(height[left], height[right])
            current_width = right - left

            # Update the maximum area if the current area is larger.
            max_area = max(max_area, current_height * current_width)

            # Move the pointer of the shorter line inward.
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return max_area
        """ Proof by Contradiction:

        Assume there's a better solution that the algorithm did not consider. This solution must involve a pair of lines that were never chosen as the outermost pair in any step.
        However, this is impossible since the algorithm begins with the widest possible container and only moves inward, considering every possible wider pair before any narrower pair. Therefore, such a pair does not exist, proving that the greedy solution is indeed optimal. """

from collections import defaultdict

class Solution:
    def characterReplacement(self, word: str, k: int) -> int:
        # Initialize a hashmap to keep track of character counts in the current window
        char_count = defaultdict(int)

        # Initialize pointers for sliding window
        left, right = 0, 0
        max_length = 0

        # Iterate through the string with the right pointer
        while right < len(word):
            # Include the current character in the window and update its count
            char_count[word[right]] += 1

            # If the window is invalid (more than k replacements needed), shrink it from the left
            while (right - left + 1) - max(char_count.values()) > k:
                char_count[word[left]] -= 1
                left += 1

            # Update the maximum window size
            max_length = max(max_length, right - left + 1)
            # Move the right pointer to expand the window
            right += 1

        return max_length

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        left = res = 0
        unique = set()
        
        for right in range(0, len(s)):
            
            while s[right] in unique:
                unique.remove(s[left])
                left = left+1
            
            unique.add(s[right])
            res=max(right-left+1,res)
                  
        return res

No answer provided.

from collections import defaultdict

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        # Edge case: If s1 is longer than s2, s1 can't be a permutation of any substring
        if len(s1) > len(s2):
            return False

        # Initialize frequency maps for s1 and for the current window in s2
        s1_map = defaultdict(int)
        window_map = defaultdict(int)

        # Build the frequency map for s1
        for char in s1:
            s1_map[char] += 1

        # Initialize the sliding window pointers
        left = 0

        # Expand the window with the right pointer
        for right in range(len(s2)):
            # Include the new character in the window map
            window_map[s2[right]] += 1

            # Shrink the window from the left if its size exceeds len(s1)
            if right - left + 1 > len(s1):
                window_map[s2[left]] -= 1
                if window_map[s2[left]] == 0:
                    del window_map[s2[left]]  # Clean up to ensure accurate comparison
                left += 1

            # If the window size matches s1 and the frequency maps match, we found a valid permutation
            if right - left + 1 == len(s1) and window_map == s1_map:
                return True

        # No permutation of s1 found in s2
        return False

No answer provided.

class Solution:
    def trap(self, height: List[int]) -> int:
        # If the list is empty, no water is trapped.
        if not height:
            return 0
        
        n = len(height)
        water = 0
        
        # Create arrays to store the maximum height to the left and right of each index.
        left_max = [0] * n
        right_max = [0] * n
        
        # Build the left_max array.
        # left_max[i] contains the maximum height from the start to index i.
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])
        
        # Build the right_max array.
        # right_max[i] contains the maximum height from index i to the end.
        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])
        
        # Calculate the trapped water at each index.
        for i in range(n):
            # The water level at index i is determined by the shorter of the two boundaries.
            water += min(left_max[i], right_max[i]) - height[i]
        
        return water

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        low = 0
        high = len(numbers) - 1
        while low < high:
            sum = numbers[low] + numbers[high]

            if sum == target:
                return [low + 1, high + 1]
            elif sum < target:
                low += 1
            else:
                high -= 1
        # In case there is no solution, return [-1, -1].
        return [-1, -1]

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        left, right = 0, len(s) - 1

        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1

            if s[left] != s[right]:      # compare once pointers are valid
                return False
            left += 1
            right -= 1

        return True