DSA MASTERY SERIES · ARRAYS & POINTERS
Array
Problem
11
Patterns
Brute Force → Optimal · Java Edition · Vol. II
NAVIGATION
Table of Contents
01 Container With Most Water Array Two Pointer O(n)
02 3Sum Array Two Pointer O(n²)
03 Two Sum II Array Two Pointer O(n)
04 Remove Duplicates I Array Two Pointer O(1) space
05 Remove Duplicates II Array Two Pointer O(1) space
06 Sort Colors Array Dutch Flag O(n)
07 Valid Palindrome String Two Pointer O(n)
08 Is Subsequence String Two Pointer O(n)
09 Intersection of Two Arrays Array HashMap O(n)
10 Reverse Words in a String String Two Pointer O(n)
ARRAY DSA MASTERY · JAVA TOC
01 Container With Most Water
MEDIUM Array Two Pointer
PROBLEM STATEMENT
Given n non-negative integers representing heights of lines,
find two lines that together with the x-axis forms a container
that holds the most water. Return the maximum water area.
EXAMPLE
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Reason: Lines at index 1 (h=8) and 8 (h=7) → min(8,7) × 7 = 49
▲ Brute Force — Check All Pairs
Check All Pairs approach:
Java
public int maxArea(int[] height) {
int max = 0;
for (int i = 0; i < [Link]; i++) {
for (int j = i + 1; j < [Link]; j++) {
int area = [Link](height[i], height[j]) * (j - i);
max = [Link](max, area);
}
}
return max;
}
TIME O(n²) SPACE O(1)
CONTAINER
■ Optimal — Two Pointer — Shrink from Ends
Two Pointer — Shrink from Ends approach:
Java
public int maxArea(int[] height) {
int left = 0, right = [Link] - 1, max = 0;
while (left < right) {
int area = [Link](height[left], height[right]) * (right - left);
max = [Link](max, area);
if (height[left] < height[right]) left++;
else right--;
}
return max;
}
TIME O(n) SPACE O(1)
ARRAY DSA MASTERY · JAVA 01
02 3Sum
MEDIUM Array Two Pointer Sorting
PROBLEM STATEMENT
Given an integer array nums, return all triplets [nums[i],nums[j],nums[k]]
such that i≠j, i≠k, j≠k, and nums[i]+nums[j]+nums[k] == 0.
The solution set must not contain duplicate triplets.
EXAMPLE
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1,-1,2],[-1,0,1]]
▲ Brute Force — Triple Nested Loops
Triple Nested Loops approach:
Java
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> res = new HashSet<>();
[Link](nums);
for (int i = 0; i < [Link] - 2; i++)
for (int j = i+1; j < [Link] - 1; j++)
for (int k = j+1; k < [Link]; k++)
if (nums[i]+nums[j]+nums[k] == 0)
[Link]([Link](nums[i],nums[j],nums[k]));
return new ArrayList<>(res);
}
TIME O(n³) SPACE O(n)
■ Optimal — Sort + Two Pointer
3SUM
Sort + Two Pointer approach:
Java
public List<List<Integer>> threeSum(int[] nums) {
[Link](nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < [Link] - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // skip dup
int l = i+1, r = [Link] - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) { [Link]([Link](nums[i],nums[l++],nums[r--]));
while (l<r && nums[l]==nums[l-1]) l++; }
else if (sum < 0) l++; else r--;
}
}
return res;
}
TIME O(n²) SPACE O(1)
ARRAY DSA MASTERY · JAVA 02
03 Two Sum II — Input Array Is Sorted
MEDIUM Array Two Pointer
PROBLEM STATEMENT
Given a 1-indexed sorted array, find two numbers that add up to target.
Return their indices as [index1, index2] (1-indexed).
Use only constant extra space.
EXAMPLE
Input: numbers = [2,7,11,15], target = 9
Output: [1, 2]
Reason: numbers[1] + numbers[2] = 2 + 7 = 9
▲ Brute Force — Nested Loop Search
Nested Loop Search approach:
Java
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < [Link]; i++)
for (int j = i + 1; j < [Link]; j++)
if (numbers[i] + numbers[j] == target)
return new int[]{ i + 1, j + 1 };
return new int[]{};
}
TIME O(n²) SPACE O(1)
■ Optimal — Two Pointer (exploit sorted order)
Two Pointer (exploit sorted order) approach:
TWO SUM II
Java
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = [Link] - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) return new int[]{ left+1, right+1 };
else if (sum < target) left++;
else right--;
}
return new int[]{};
}
TIME O(n) SPACE O(1)
ARRAY DSA MASTERY · JAVA 03
04 Remove Duplicates from Sorted Array
EASY Array Two Pointer
PROBLEM STATEMENT
Given a sorted array, remove duplicates in-place so each element
appears only once. Return the number of unique elements k.
The first k elements must hold the result; order doesn't matter beyond.
EXAMPLE
Input: nums = [1, 1, 2]
Output: 2, nums = [1, 2, _]
Input: nums = [0,0,1,1,1,2,2,3,3,4] → Output: 5
▲ Brute Force — Temporary Set Copy-Back
Temporary Set Copy-Back approach:
Java
public int removeDuplicates(int[] nums) {
Set<Integer> seen = new LinkedHashSet<>();
for (int n : nums) [Link](n);
int i = 0;
for (int n : seen) nums[i++] = n;
return [Link]();
}
TIME O(n) SPACE O(n)
■ Optimal — Slow/Fast Two Pointer
Slow/Fast Two Pointer approach:
DEDUP I
Java
public int removeDuplicates(int[] nums) {
int k = 1;
for (int i = 1; i < [Link]; i++) {
if (nums[i] != nums[i - 1]) {
nums[k++] = nums[i];
}
}
return k;
}
TIME O(n) SPACE O(1)
ARRAY DSA MASTERY · JAVA 04
05 Remove Duplicates II — Allow At Most Twice
MEDIUM Array Two Pointer
PROBLEM STATEMENT
Same as Remove Duplicates, but each unique element may appear at most twice.
Return the count k; first k elements must hold the result in-place.
EXAMPLE
Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
▲ Brute Force — Count Map + Rebuild
Count Map + Rebuild approach:
Java
public int removeDuplicates(int[] nums) {
int k = 0;
int[] temp = new int[[Link]];
Map<Integer,Integer> cnt = new LinkedHashMap<>();
for (int n : nums) [Link](n, 1, Integer::sum);
for (var e : [Link]())
for (int t = 0; t < [Link]([Link](), 2); t++)
temp[k++] = [Link]();
[Link](temp, 0, nums, 0, k);
return k;
}
TIME O(n) SPACE O(n)
■ Optimal — Two Pointer — Compare k-2
DEDUP II
Two Pointer — Compare k-2 approach:
Java
public int removeDuplicates(int[] nums) {
int k = 0;
for (int n : nums) {
// allow if fewer than 2 written, or current != nums[k-2]
if (k < 2 || n != nums[k - 2]) {
nums[k++] = n;
}
}
return k;
}
TIME O(n) SPACE O(1)
ARRAY DSA MASTERY · JAVA 05
06 Sort Colors (Dutch National Flag)
MEDIUM Array Three Pointer
PROBLEM STATEMENT
Given an array with values 0 (red), 1 (white), 2 (blue),
sort it in-place so all 0s come first, then 1s, then 2s.
You must not use the library's sort function.
EXAMPLE
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
▲ Brute Force — Count then Fill
Count then Fill approach:
Java
public void sortColors(int[] nums) {
int c0 = 0, c1 = 0, c2 = 0;
for (int n : nums) { if(n==0)c0++; else if(n==1)c1++; else c2++; }
int i = 0;
while (c0-- > 0) nums[i++] = 0;
while (c1-- > 0) nums[i++] = 1;
while (c2-- > 0) nums[i++] = 2;
}
TIME O(n) SPACE O(1)
■ Optimal — Dutch Flag — One Pass Three Pointers
Dutch Flag — One Pass Three Pointers approach:
SORT COLORS
Java
public void sortColors(int[] nums) {
int lo = 0, mid = 0, hi = [Link] - 1;
while (mid <= hi) {
if (nums[mid] == 0) swap(nums, lo++, mid++);
else if (nums[mid] == 1) mid++;
else swap(nums, mid, hi--); // 2: swap to hi
}
}
private void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
TIME O(n) SPACE O(1)
ARRAY DSA MASTERY · JAVA 06
07 Valid Palindrome
EASY String Two Pointer
PROBLEM STATEMENT
A phrase is a palindrome if, after converting all uppercase letters to lowercase
and removing all non-alphanumeric characters, it reads the same forward and backward.
Given a string s, return true if it is a palindrome, false otherwise.
EXAMPLE
Input: s = "A man, a plan, a canal: Panama"
Output: true
Input: s = "race a car" → Output: false
▲ Brute Force — Clean then Compare
Clean then Compare approach:
Java
public boolean isPalindrome(String s) {
String clean = [Link]().replaceAll("[^a-z0-9]", "");
String rev = new StringBuilder(clean).reverse().toString();
return [Link](rev);
}
TIME O(n) SPACE O(n)
■ Optimal — Two Pointer — Skip Non-Alphanumeric
Two Pointer — Skip Non-Alphanumeric approach:
Java
PALINDROME
public boolean isPalindrome(String s) {
int l = 0, r = [Link]() - 1;
while (l < r) {
while (l < r && )) l++;
while (l < r && )) r--;
if ([Link]([Link](l)) !=
[Link]([Link](r))) return false;
l++; r--;
}
return true;
}
TIME O(n) SPACE O(1)
ARRAY DSA MASTERY · JAVA 07
08 Is Subsequence
EASY String Two Pointer
PROBLEM STATEMENT
Given two strings s and t, return true if s is a subsequence of t.
A subsequence is formed by deleting some (or no) characters from t
without disturbing the relative order of the remaining characters.
EXAMPLE
Input: s = "ace", t = "abcde"
Output: true (a→b→c→d→e contains a,c,e in order)
Input: s = "aec", t = "abcde" → Output: false
▲ Brute Force — Recursive / DP Approach
Recursive / DP Approach approach:
Java
public boolean isSubsequence(String s, String t) {
if ([Link]()) return true;
if ([Link]()) return false;
if ([Link](0) == [Link](0))
return isSubsequence([Link](1), [Link](1));
return isSubsequence(s, [Link](1));
}
TIME O(n) SPACE O(n) stack
■ Optimal — Two Pointer — Single Pass
Two Pointer — Single Pass approach:
SUBSEQUENCE
Java
public boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < [Link]() && j < [Link]()) {
if ([Link](i) == [Link](j)) i++;
j++;
}
return i == [Link]();
}
TIME O(n) SPACE O(1)
ARRAY DSA MASTERY · JAVA 08
09 Intersection of Two Arrays
EASY Array HashMap Set
PROBLEM STATEMENT
Given two integer arrays nums1 and nums2, return an array of their intersection.
Each element in the result must appear as many times as it shows in both arrays.
The result can be in any order.
EXAMPLE
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2, 2]
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] → Output: [4, 9]
▲ Brute Force — Nested Loop Check
Nested Loop Check approach:
Java
public int[] intersect(int[] nums1, int[] nums2) {
List<Integer> res = new ArrayList<>();
boolean[] used = new boolean[[Link]];
for (int a : nums1)
for (int j = 0; j < [Link]; j++)
if (!used[j] && a == nums2[j]) {
[Link](a); used[j] = true; break;
}
return [Link]().mapToInt(Integer::intValue).toArray();
}
TIME O(m×n) SPACE O(min(m,n))
INTERSECTION
■ Optimal — HashMap Count
HashMap Count approach:
Java
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer,Integer> map = new HashMap<>();
for (int n : nums1) [Link](n, 1, Integer::sum);
List<Integer> res = new ArrayList<>();
for (int n : nums2)
if ([Link](n, 0) > 0) {
[Link](n);
[Link](n, -1, Integer::sum);
}
return [Link]().mapToInt(Integer::intValue).toArray();
}
TIME O(m+n) SPACE O(min(m,n))
ARRAY DSA MASTERY · JAVA 09
10 Reverse Words in a String
MEDIUM String Two Pointer
PROBLEM STATEMENT
Given a string s, reverse the order of the words.
A word is a sequence of non-space characters. Words are separated by at least one space.
Return the reversed string with single spaces and no leading/trailing spaces.
EXAMPLE
Input: s = " the sky is blue "
Output: "blue is sky the"
Input: s = "a good example" → Output: "example good a"
▲ Brute Force — Split + Reverse + Join
Split + Reverse + Join approach:
Java
public String reverseWords(String s) {
String[] words = [Link]().split("\\s+");
int l = 0, r = [Link] - 1;
while (l < r) {
String tmp = words[l]; words[l] = words[r]; words[r] = tmp;
l++; r--;
}
return [Link](" ", words);
}
TIME O(n) SPACE O(n)
■ Optimal — Deque — Push/Pop Words
REV WORDS
Deque — Push/Pop Words approach:
Java
public String reverseWords(String s) {
Deque<String> dq = new ArrayDeque<>();
int n = [Link](), i = 0;
while (i < n) {
while (i < n && [Link](i) == ' ') i++;
if (i == n) break;
int j = i;
while (j < n && [Link](j) != ' ') j++;
[Link]([Link](i, j)); // push to front
i = j;
}
return [Link](" ", dq);
}
TIME O(n) SPACE O(n)
ARRAY DSA MASTERY · JAVA 10