1) First Non-Repeating Character in a String
Problem Statement: Given a string s, return the index of the first non-repeating character. If none exists, return -1.
Intuition / How to Approach: Count character frequencies, then return the first index whose frequency is 1. The
brute force re-checks equality for each char; optimized uses a frequency map.
■ Brute Force Solution
For every character at i, scan the string and verify it doesn't match any other character.
public class FirstUniqueChar {
// Brute Force
public static int firstUniqCharBrute(String s) {
for (int i = 0; i < s.length(); i++) {
boolean unique = true;
for (int j = 0; j < s.length(); j++) {
if (i != j && s.charAt(i) == s.charAt(j)) {
unique = false; break;
}
}
if (unique) return i;
}
return -1;
}
// Demo
public static void main(String[] args) {
System.out.println(firstUniqCharBrute("leetcode")); // 0
}
}
■ Time: O(n^2) ■ Space: O(1)
■ Optimized Solution
Use an int[26] or HashMap to count frequencies in O(n), then scan again to find index with count 1.
import java.util.*;
public class FirstUniqueCharOptimized {
public static int firstUniqChar(String s) {
int[] freq = new int[26];
for (int i = 0; i < s.length(); i++) freq[s.charAt(i) - 'a']++;
for (int i = 0; i < s.length(); i++) if (freq[s.charAt(i) - 'a'] == 1) return i;
return -1;
}
public static void main(String[] args) {
System.out.println(firstUniqChar("swiss")); // 1 -> 'w'
}
}
■ Time: O(n) ■ Space: O(1) (fixed alphabet) / O(k) for general charset
2) Insert Interval & Merge Overlaps
Problem Statement: You are given a list of non-overlapping intervals sorted by start time. Insert a new interval and
merge overlaps.
Intuition / How to Approach: Since intervals are sorted, add all intervals that end before the new one, merge
overlaps in one pass, then append the remaining.
■ Brute Force Solution
Append the new interval, sort all intervals by start, then merge sequentially.
import java.util.*;
public class InsertIntervalBrute {
public static int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
list.add(newInterval);
list.sort(Comparator.comparingInt(a -> a[0]));
List<int[]> merged = new ArrayList<>();
for (int[] it : list) {
if (merged.isEmpty() || merged.get(merged.size()-1)[1] < it[0]) {
merged.add(it);
} else {
merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], it[1]);
}
}
return merged.toArray(new int[merged.size()][]);
}
public static void main(String[] args) {
int[][] res = insert(new int[][]{{1,3},{6,9}}, new int[]{2,5});
System.out.println(Arrays.deepToString(res)); // [[1,5], [6,9]]
}
}
■ Time: O(n log n) (sorting) ■ Space: O(n)
■ Optimized Solution
Without sorting again: add all intervals ending before newInterval, then merge overlaps while they intersect, then
append the rest.
import java.util.*;
public class InsertIntervalOptimized {
public static int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res = new ArrayList<>();
int i = 0, n = intervals.length;
while (i < n && intervals[i][1] < newInterval[0]) res.add(intervals[i++]);
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
res.add(newInterval);
while (i < n) res.add(intervals[i++]);
return res.toArray(new int[res.size()][]);
}
public static void main(String[] args) {
int[][] res = insert(new int[][]{{1,3},{6,9}}, new int[]{2,5});
System.out.println(Arrays.deepToString(res)); // [[1,5], [6,9]]
}
}
■ Time: O(n) ■ Space: O(n)
3) Longest Substring Without Repeating Characters
Problem Statement: Given a string s, find the length of the longest substring without repeating characters.
Intuition / How to Approach: Maintain a sliding window [left..right]. If char repeats, move left to one past its last
index.
■ Brute Force Solution
Try all substrings expanding from each i until a repeat occurs.
import java.util.*;
public class LongestSubstringBrute {
public static int lengthOfLongestSubstring(String s) {
int n = s.length(), maxLen = 0;
for (int i = 0; i < n; i++) {
boolean[] seen = new boolean[256];
for (int j = i; j < n; j++) {
char c = s.charAt(j);
if (seen[c]) break;
seen[c] = true;
maxLen = Math.max(maxLen, j - i + 1);
}
}
return maxLen;
}
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
}
}
■ Time: O(n^2) ■ Space: O(1) / O(k)
■ Optimized Solution
Use a map of char -> last index. Move left pointer to max(left, lastIndex+1) when repeat found.
import java.util.*;
public class LongestSubstringOptimized {
public static int lengthOfLongestSubstring(String s) {
int[] last = new int[256];
Arrays.fill(last, -1);
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last[c] >= left) left = last[c] + 1;
last[c] = right;
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("pwwkew")); // 3
}
}
■ Time: O(n) ■ Space: O(1) / O(k)
4) Two Sum
Problem Statement: Given an array nums and an integer target, return indices of the two numbers such that they
add to target.
Intuition / How to Approach: Store seen numbers in a map: need = target - num. If need in map, return indices.
■ Brute Force Solution
Check all pairs (i, j).
import java.util.*;
public class TwoSumBrute {
public static int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) return new int[]{i, j};
}
}
return new int[]{};
}
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[]{2,7,11,15}, 9))); // [0,1]
}
}
■ Time: O(n^2) ■ Space: O(1)
■ Optimized Solution
Use HashMap to check complement in O(1) average.
import java.util.*;
public class TwoSumOptimized {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (map.containsKey(need)) return new int[]{map.get(need), i};
map.put(nums[i], i);
}
return new int[]{};
}
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[]{3,2,4}, 6))); // [1,2]
}
}
■ Time: O(n) ■ Space: O(n)
5) Number of Islands (DFS/BFS)
Problem Statement: Given a 2D grid of '1's (land) and '0's (water), count the number of islands.
Intuition / How to Approach: Traverse all cells; when you find land, run DFS/BFS to mark the entire island visited.
■ Brute Force Solution
Use a visited[][] array to avoid revisiting; run DFS for every unseen land cell.
import java.util.*;
public class NumberOfIslandsBrute {
static int rows, cols;
public static int numIslands(char[][] grid) {
rows = grid.length; cols = grid[0].length;
boolean[][] vis = new boolean[rows][cols];
int count = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1' && !vis[r][c]) {
dfs(grid, vis, r, c);
count++;
}
}
}
return count;
}
static void dfs(char[][] g, boolean[][] vis, int r, int c) {
if (r<0 || c<0 || r>=rows || c>=cols || g[r][c]=='0' || vis[r][c]) return;
vis[r][c] = true;
dfs(g, vis, r+1,c); dfs(g, vis, r-1,c); dfs(g, vis, r,c+1); dfs(g, vis, r,c-1);
}
public static void main(String[] args) {
char[][] grid = {{'1','1','0'},{'0','1','0'},{'1','0','1'}};
System.out.println(numIslands(grid)); // 3
}
}
■ Time: O(R*C) ■ Space: O(R*C) visited + recursion stack
■ Optimized Solution
Mutate grid in-place (mark visited by flipping '1'→'0'), which saves extra visited[][] space.
public class NumberOfIslandsOptimized {
static int rows, cols;
public static int numIslands(char[][] grid) {
rows = grid.length; cols = grid[0].length;
int count = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
dfs(grid, r, c);
count++;
}
}
}
return count;
}
static void dfs(char[][] g, int r, int c) {
if (r<0 || c<0 || r>=rows || c>=cols || g[r][c]=='0') return;
g[r][c] = '0';
dfs(g, r+1,c); dfs(g, r-1,c); dfs(g, r,c+1); dfs(g, r,c-1);
}
public static void main(String[] args) {
char[][] grid = {{'1','1','0'},{'0','1','0'},{'1','0','1'}};
System.out.println(numIslands(grid)); // 3
}
}
■ Time: O(R*C) ■ Space: O(1) extra (mutating grid) + recursion stack
6) Maximum Subarray Sum (Kadane’s Algorithm)
Problem Statement: Given an integer array nums, find the contiguous subarray with the largest sum and return the
sum.
Intuition / How to Approach: Either extend the previous sum or start fresh at current element; keep a global
maximum.
■ Brute Force Solution
Compute sum of every subarray using nested loops; track the maximum.
public class MaxSubarrayBrute {
public static int maxSubArray(int[] nums) {
int maxSum = nums[0];
for (int i = 0; i < nums.length; i++) {
int cur = 0;
for (int j = i; j < nums.length; j++) {
cur += nums[j];
maxSum = Math.max(maxSum, cur);
}
}
return maxSum;
}
public static void main(String[] args) {
System.out.println(maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4})); // 6
}
}
■ Time: O(n^2) ■ Space: O(1)
■ Optimized Solution
Kadane’s: cur = max(num, cur + num); maxSum = max(maxSum, cur).
public class MaxSubarrayOptimized {
public static int maxSubArray(int[] nums) {
int cur = nums[0], maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
maxSum = Math.max(maxSum, cur);
}
return maxSum;
}
public static void main(String[] args) {
System.out.println(maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4})); // 6
}
}
■ Time: O(n) ■ Space: O(1)
