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.