LeetCode - Two Pointers - Two Sum II/ Reverse String/ Remove Duplicates from Sorted Array/ Container With Most Water

✅ Problem 1: Two Sum II – Input Array Is Sorted

🔹 Problem:

Given a sorted array of integers numbers and a target, return indices (1-based) of the two numbers such that they add up to the target.

---

🔸 Example:

Input: numbers = [2, 7, 11, 15], target = 9  
Output: [1, 2]

---

🔹 Brute Force (O(n²))

for (int i = 0; i < numbers.size(); i++) {
    for (int j = i + 1; j < numbers.size(); j++) {
        if (numbers[i] + numbers[j] == target)
            return {i + 1, j + 1};
    }
}

i	j	numbers[i]	numbers[j]	sum	sum == 9?
0	1	2	7	9	✅ Yes

---

✅ Optimized: Two Pointers (O(n))

int left = 0, right = numbers.size() - 1;
while (left < right) {
    int sum = numbers[left] + numbers[right];
    if (sum == target) return {left + 1, right + 1};
    else if (sum < target) left++;
    else right--;
}

Left	Right	numbers[left]	numbers[right]	sum	Action
0	3	2	15	17	sum > target → right--
0	2	2	11	13	right--
0	1	2	7	9	✅ Return [1, 2]

---

✅ Problem 2: Reverse String

🔹 Problem:

Reverse the string s in-place.

---

🔸 Brute Force (O(n), but using extra space)

string reversed = "";
for (int i = s.length() - 1; i >= 0; i--) {
    reversed += s[i];
}
s = reversed;

---

✅ Two Pointers (O(n), in-place)

int left = 0, right = s.size() - 1;
while (left < right) {
    swap(s[left++], s[right--]);
}

Example: s = "hello"

Left	Right	s[Left]	s[Right]	After Swap
0	4	h	o	oellh
1	3	e	l	olleh
2	2	l	l	Done

---

✅ Problem 3: Remove Duplicates from Sorted Array

🔹 Problem:

Given a sorted array, remove the duplicates in-place such that each element appears only once and return the new length. Do not allocate extra space.

---

🔹 Input

nums = [0, 0, 1, 1, 1, 2, 2, 3, 4]

---

🔸 Brute Force (❌ Not allowed in interviews for this problem)

vector<int> temp;
for (int i = 0; i < nums.size(); ++i) {
    if (i == 0 || nums[i] != nums[i - 1])
        temp.push_back(nums[i]);
}
nums = temp;
return temp.size();

🧾 Output:

nums = [0, 1, 2, 3, 4]   // New vector
return 5

❌ This uses extra space (temp), which is not allowed by the problem constraints.

---

✅ Two Pointers (In-place, O(n))

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;

    int i = 0; // Slow pointer (last unique element index)
    for (int j = 1; j < nums.size(); j++) { // Fast pointer
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

---

🧾 Input:

nums = [0, 0, 1, 1, 1, 2, 2, 3, 4]

🔁 Iteration Table:

j (fast)	i (slow)	nums[j]	nums[i]	nums (after possible update)
1	0	0	0	[0, 0, 1, 1, 1, 2, 2, 3, 4]
2	0	1	0	[0, 1, 1, 1, 1, 2, 2, 3, 4]
3	1	1	1	[0, 1, 1, 1, 1, 2, 2, 3, 4]
4	1	1	1
5	1	2	1	[0, 1, 2, 1, 1, 2, 2, 3, 4]
6	2	2	2
7	2	3	2	[0, 1, 2, 3, 1, 2, 2, 3, 4]
8	3	4	3	[0, 1, 2, 3, 4, 2, 2, 3, 4]

---

🧾 Output:

nums = [0, 1, 2, 3, 4, _, _, _, _] // After i + 1 = 5
return 5

The contents beyond index 4 can be anything — only the first 5 elements are guaranteed to be the unique sorted elements.

---

💡 Summary

Method	Time Complexity	Space Complexity	In-place?	Return
Brute Force	O(n)	O(n)	❌	New vector
Two Pointers	O(n)	O(1)	✅	Index + 1

---

✅ Problem 4: Container With Most Water

🔹 Problem:

Find the max area of water container formed by two lines in height array.

---

🔸 Brute Force (O(n²))

int maxArea = 0;
for (int i = 0; i < height.size(); i++) {
    for (int j = i + 1; j < height.size(); j++) {
        int area = (j - i) * min(height[i], height[j]);
        maxArea = max(maxArea, area);
    }
}

---

✅ Two Pointers (O(n))

int left = 0, right = height.size() - 1;
int maxArea = 0;
while (left < right) {
    int h = min(height[left], height[right]);
    int w = right - left;
    maxArea = max(maxArea, h * w);
    if (height[left] < height[right]) left++;
    else right--;
}

Example: height = [1,8,6,2,5,4,8,3,7]

Left	Right	height[L]	height[R]	Area	maxArea	Action
0	8	1	7	8	8	left++
1	8	8	7	49	49	right--
1	7	8	3	18	49	right--
1	6	8	8	40	49	right--
1	5	8	4	16	49	right--

.