Two Pointers

Container With Most Water

Link: https://leetcode.com/problems/container-with-most-water/

Code:

class Solution {
    public int maxArea(int[] height) {
        int max_area = 0, area = 0;
        int n = height.length;
        int left = 0, right = n - 1;
        while( left < right) {
            area = Math.min(height[right], height[left]) * (right - left);
            max_area = Math.max(max_area, area);
            if (height[left] < height[right]) {
                left ++;
            } else {
                right --;
            }
        }
        return max_area;
    }
}

  • Two pointers;

  • Time complexity: O(n);

Remove Nth Node From End of List

Link: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = dummy, second = dummy;
        // move first pointer
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }
        // move first and second pointer
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}

  • add an auxiliary "dummy" node;

  • two pointers;

  • Time complexity: O(L), where L is the length of the list;

Reverse Vowels of a String

Link: https://leetcode.com/problems/reverse-vowels-of-a-string/

To solve the problem of reversing only the vowels in a given string, we can use a two-pointer approach. Here's a step-by-step breakdown of the solution:

  1. Identify Vowels: First, identify what constitutes a vowel. For this problem, the vowels are 'a', 'e', 'i', 'o', 'u' (both lowercase and uppercase).

  2. Two-Pointer Technique: Use two pointers, one starting from the beginning of the string and the other from the end. Move these pointers towards each other:

    • The left pointer moves to the right until it finds a vowel.

    • The right pointer moves to the left until it finds a vowel.

    • Swap the vowels at these pointers.

  3. Continue the Process: Continue the process until the two pointers meet or cross each other.

Here's the Python code to achieve this:

def reverseVowels(s: str) -> str:
    vowels = set('aeiouAEIOU')
    s = list(s)  # Convert string to list to modify it
    left, right = 0, len(s) - 1

    while left < right:
        if s[left] not in vowels:
            left += 1
        elif s[right] not in vowels:
            right -= 1
        else:
            # Swap the vowels
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

    return ''.join(s)  # Convert list back to string

# Examples to test the function
print(reverseVowels("hello"))  # Output: "holle"
print(reverseVowels("leetcode"))  # Output: "leotcede"

Explanation:

  • Line 1: Define the function reverseVowels which takes a string s as input.

  • Line 2: Create a set of vowels for quick lookup.

  • Line 3: Convert the string to a list since strings are immutable in Python.

  • Line 4: Initialize two pointers, left at the start and right at the end of the list.

  • Lines 6-15: Loop until the two pointers meet or cross.

  • Lines 7-9: Move the left pointer to the right if the current character is not a vowel.

  • Lines 10-12: Move the right pointer to the left if the current character is not a vowel.

  • Lines 13-15: If both pointers point to vowels, swap them and move both pointers towards the center.

  • Line 17: Convert the list back to a string and return it.

This approach ensures that we only traverse the string once, making the solution efficient with a time complexity of O(n), where n is the length of the string.

String Compression

Link: https://leetcode.com/problems/string-compression/

Google Gemini answer:

This is a classic in-place modification problem. Since you prefer Python, I'll provide a solution in Python.

The core idea is to use two pointers: one for reading the input array and one for writing to the modified array.

Here's the algorithm:

  1. Initialize read_ptr to 0 (the pointer for reading the input array) and write_ptr to 0 (the pointer for writing to the modified array).

  2. Iterate with read_ptr through the chars array.

  3. Inside the loop, for each character chars[read_ptr], count its consecutive occurrences.

  4. Store the character at chars[write_ptr] and increment write_ptr.

  5. If the count of consecutive occurrences is greater than 1, convert the count to a string, then iterate through its digits. For each digit, store it at chars[write_ptr] and increment write_ptr.

  6. Update read_ptr to the next distinct character's position.

  7. After the loop finishes, write_ptr will hold the new length of the compressed array.

Let's break down the counting and writing of the number:

If the count is 12, you need to write '1' then '2'. A simple way to do this is to convert the count to a string and then iterate through its characters.

Here's the Python code:

class Solution:
    def compress(self, chars: list[str]) -> int:
        read_ptr = 0  # Pointer for reading the input array
        write_ptr = 0  # Pointer for writing to the compressed array

        n = len(chars)

        while read_ptr < n:
            current_char = chars[read_ptr]
            count = 0

            # Count consecutive occurrences of current_char
            while read_ptr < n and chars[read_ptr] == current_char:
                count += 1
                read_ptr += 1

            # Write the character
            chars[write_ptr] = current_char
            write_ptr += 1

            # If count is greater than 1, write the count
            if count > 1:
                # Convert count to string and write each digit
                for digit in str(count):
                    chars[write_ptr] = digit
                    write_ptr += 1
        
        return write_ptr

Move Zeros

Link: https://leetcode.com/problems/move-zeroes/

Google Gemini answer:

Here's a Python solution for the LeetCode "Move Zeroes" problem:

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        # Pointer for the position to place the next non-zero element
        non_zero_ptr = 0

        # Iterate through the array with a 'current' pointer
        for current_ptr in range(len(nums)):
            # If the current element is not zero
            if nums[current_ptr] != 0:
                # Place it at the 'non_zero_ptr' position
                nums[non_zero_ptr] = nums[current_ptr]
                # Increment the non_zero_ptr to the next available slot
                non_zero_ptr += 1
        
        # After placing all non-zero elements, fill the remaining positions with zeros
        for i in range(non_zero_ptr, len(nums)):
            nums[i] = 0

Explanation of the approach:

The solution uses a two-pointer approach, which is a common and efficient technique for in-place array modifications.

  1. non_zero_ptr: This pointer keeps track of where the next non-zero element should be placed. It starts at the beginning of the array (index 0).

  2. current_ptr: This pointer iterates through the entire array from left to right.

How it works:

  • As current_ptr iterates, if it encounters a non-zero element (nums[current_ptr] != 0), that element is moved to the position indicated by non_zero_ptr. Then, non_zero_ptr is incremented, effectively preparing for the next non-zero element.

  • If current_ptr encounters a zero, nothing is done with it in this first pass. The non_zero_ptr remains where it is, waiting for the next non-zero number. This implicitly "skips" the zero, effectively moving it to the end.

  • After the first loop completes, all non-zero elements will be at the beginning of the array, maintaining their relative order. The non_zero_ptr will now point to the first position that should contain a zero.

  • The second loop then fills all positions from non_zero_ptr to the end of the array with zeros.

Example walkthrough (nums = [0,1,0,3,12]):

  1. nums = [0,1,0,3,12], non_zero_ptr = 0

  2. current_ptr = 0, nums[0] = 0. Do nothing.

  3. current_ptr = 1, nums[1] = 1. Not zero.nums[non_zero_ptr] (i.e., nums[0]) becomes 1.nums is now [1,1,0,3,12].non_zero_ptr becomes 1.

  4. current_ptr = 2, nums[2] = 0. Do nothing.

  5. current_ptr = 3, nums[3] = 3. Not zero.nums[non_zero_ptr] (i.e., nums[1]) becomes 3.nums is now [1,3,0,3,12]. (Note: the original 1 at nums[1] was overwritten, but it was already "processed" by being moved to nums[0]).non_zero_ptr becomes 2.

  6. current_ptr = 4, nums[4] = 12. Not zero.nums[non_zero_ptr] (i.e., nums[2]) becomes 12.nums is now [1,3,12,3,12].non_zero_ptr becomes 3.

  7. End of first loop. nums is [1,3,12,3,12], non_zero_ptr = 3.

  8. Second loop: range(non_zero_ptr, len(nums)) which is range(3, 5).

    • i = 3: nums[3] = 0. nums becomes [1,3,12,0,12].

    • i = 4: nums[4] = 0. nums becomes [1,3,12,0,0].

Final nums: [1,3,12,0,0]

Time and Space Complexity:

  • Time Complexity: $O(N)$

    • The first loop iterates through the array once.

    • The second loop iterates through the remaining portion of the array.

    • Therefore, the total operations are proportional to the length of the array, N.

  • Space Complexity: $O(1)$

    • The solution modifies the array in-place and does not use any additional data structures that scale with the input size.

PreviousStringNextLinked List

Last updated