NeetCode 150 - Java Solutions Cheat Sheet

Arrays & Hashing

1. Contains Duplicate

Problem: Given an array, return true if any value appears at least twice.

public boolean containsDuplicate(int[] nums) {

Set<Integer> seen = new HashSet<>();
for (int num : nums) {
if (!seen.add(num)) return true;
}
return false;
}

Solution: Use HashSet to track seen numbers. Time: O(n), Space: O(n)

2. Valid Anagram

Problem: Check if t is an anagram of s.

public boolean isAnagram(String s, String t) {

if (s.length() != t.length()) return false;

int[] freq = new int[26];

for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i) - 'a']++;
freq[t.charAt(i) - 'a']--;
}

for (int count : freq) {

if (count != 0) return false;
}
return true;
}

Solution: Use frequency array for character counting. Time: O(n), Space: O(1)

3. Two Sum

Problem: Find two numbers that add up to target.

public int[] twoSum(int[] nums, int target) {

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] {map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[0];
}

Solution: Use HashMap to store complement. Time: O(n), Space: O(n)

4. Group Anagrams

Problem: Group strings that are anagrams of each other.

 public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();

for (String str : strs) {

char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);

map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);

}

return new ArrayList<>(map.values());

}

Solution: Sort characters as key for HashMap. Time: O(n * k * log k), Space: O(n * k)

5. Top K Frequent Elements

Problem: Find k most frequent elements.

public int[] topKFrequent(int[] nums, int k) {

Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);

for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
pq.offer(new int[]{entry.getKey(), entry.getValue()});
}

int[] result = new int[k];

for (int i = 0; i < k; i++) {
result[i] = pq.poll()[0];
}
return result;
}

Solution: Use HashMap + PriorityQueue. Time: O(n log k), Space: O(n)

Two Pointers

6. Valid Palindrome

Problem: Check if string is palindrome after converting to lowercase and removing non-alphanumeric chars.
 public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;

while (left < right) {

while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}

if (Character.toLowerCase(s.charAt(left)) !=
Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}

Solution: Two pointers from ends, skip non-alphanumeric. Time: O(n), Space: O(1)

7. 3Sum

Problem: Find all unique triplets that sum to zero.

public List<List<Integer>> threeSum(int[] nums) {

Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();

for (int i = 0; i < nums.length - 2; i++) {

if (i > 0 && nums[i] == nums[i-1]) continue;

int left = i + 1;
int right = nums.length - 1;

while (left < right) {

int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}

Solution: Sort + Two pointers. Skip duplicates. Time: O(n²), Space: O(1)

NeetCode 150 - Complete Java Solutions Cheat Sheet

Arrays & Hashing (Continued)

8. Product of Array Except Self

Problem: Return array where each element is product of all other elements except self.

public int[] productExceptSelf(int[] nums) {

int n = nums.length;
int[] result = new int[n];

result[0] = 1;
for (int i = 1; i < n; i++) {
result[i] = result[i-1] * nums[i-1];
}

int right = 1;
for (int i = n-1; i >= 0; i--) {
result[i] *= right;
right *= nums[i];
}

return result;
}

Solution: Two passes - prefix and suffix products. Time: O(n), Space: O(1)

9. Encode and Decode Strings

Problem: Design an algorithm to encode/decode a list of strings.

public class Codec {

public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str.length()).append('#').append(str);
}
return sb.toString();
}

public List<String> decode(String s) {

List<String> result = new ArrayList<>();
int i = 0;

while (i < s.length()) {

int j = i;
while (s.charAt(j) != '#') j++;
int length = Integer.parseInt(s.substring(i, j));
result.add(s.substring(j + 1, j + 1 + length));
i = j + 1 + length;
}

return result;
}
}

Solution: Use length encoding with delimiter. Time: O(n), Space: O(n)

10. Longest Consecutive Sequence

Problem: Find length of longest consecutive sequence in unsorted array.

 public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) set.add(num);

int maxLength = 0;
for (int num : nums) {
if (!set.contains(num-1)) {
int currentNum = num;
int currentLength = 1;

while (set.contains(currentNum+1)) {
currentNum++;
currentLength++;
}

maxLength = Math.max(maxLength, currentLength);

}
}
return maxLength;
}

Solution: Use HashSet to check sequences. Time: O(n), Space: O(n)

Two Pointers (Continued)

11. Container With Most Water

Problem: Find two lines that form container with most water.

public int maxArea(int[] height) {

int maxArea = 0;
int left = 0;
int right = height.length - 1;

while (left < right) {

int width = right - left;
int h = Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, width * h);

if (height[left] < height[right]) {

left++;
} else {
right--;
}
}

return maxArea;
}

Solution: Two pointers from ends, move shorter line. Time: O(n), Space: O(1)

12. Trapping Rain Water

Problem: Calculate how much water can be trapped after raining.

 public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int water = 0;

while (left < right) {

if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}

return water;
}

Solution: Two pointers with max height tracking. Time: O(n), Space: O(1)

Sliding Window

13. Best Time to Buy and Sell Stock

Problem: Find maximum profit from buying and selling stock once.

public int maxProfit(int[] prices) {

int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;

for (int price : prices) {

minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}

return maxProfit;
}

Solution: Track minimum price and max profit. Time: O(n), Space: O(1)

14. Longest Substring Without Repeating Characters

Problem: Find length of longest substring without repeating characters.

 public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int maxLength = 0;
int start = 0;

for (int end = 0; end < s.length(); end++) {

char c = s.charAt(end);
if (map.containsKey(c)) {
start = Math.max(start, map.get(c) + 1);
}
map.put(c, end);
maxLength = Math.max(maxLength, end - start + 1);
}

return maxLength;
}

Solution: Sliding window with HashMap. Time: O(n), Space: O(min(m,n))

15. Longest Repeating Character Replacement

Problem: Find longest substring where any character can be replaced k times.

public int characterReplacement(String s, int k) {

int[] count = new int[26];
int maxCount = 0;
int maxLength = 0;
int start = 0;

for (int end = 0; end < s.length(); end++) {

count[s.charAt(end) - 'A']++;
maxCount = Math.max(maxCount, count[s.charAt(end) - 'A']);

if (end - start + 1 - maxCount > k) {

count[s.charAt(start) - 'A']--;
start++;
}

maxLength = Math.max(maxLength, end - start + 1);

}

return maxLength;
}

Solution: Sliding window with character count. Time: O(n), Space: O(1)

[Previous sections remain the same...]

Sliding Window (Continued)

16. Minimum Window Substring

Problem: Find minimum window in s that contains all characters of t.

 public String minWindow(String s, String t) {
if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";

Map<Character, Integer> map = new HashMap<>();

for (char c : t.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}

int start = 0, minStart = 0;

int minLen = Integer.MAX_VALUE;
int count = map.size();

for (int end = 0; end < s.length(); end++) {

char c = s.charAt(end);
if (map.containsKey(c)) {
map.put(c, map.get(c) - 1);
if (map.get(c) == 0) count--;
}

while (count == 0) {
if (end - start + 1 < minLen) {
minLen = end - start + 1;
minStart = start;
}

char startChar = s.charAt(start);

if (map.containsKey(startChar)) {
map.put(startChar, map.get(startChar) + 1);
if (map.get(startChar) > 0) count++;
}
start++;
}
}

return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);

}

Solution: Sliding window with character count. Time: O(n), Space: O(k)

17. Sliding Window Maximum

Problem: Find maximum element in each sliding window of size k.

 public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0) return new int[0];

int n = nums.length;
int[] result = new int[n-k+1];
int ri = 0;

Deque<Integer> deque = new ArrayDeque<>();

for (int i = 0; i < nums.length; i++) {
// Remove elements outside the current window
while (!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.poll();
}

// Remove elements smaller than current

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}

deque.offer(i);
if (i >= k - 1) {
result[ri++] = nums[deque.peek()];
}
}

return result;
}

Solution: Use deque to maintain decreasing sequence. Time: O(n), Space: O(k)

Stack

18. Valid Parentheses

Problem: Check if string has valid parentheses.

public boolean isValid(String s) {

Stack<Character> stack = new Stack<>();

for (char c : s.toCharArray()) {

if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
if (c == ')' && stack.peek() != '(') return false;
if (c == '}' && stack.peek() != '{') return false;
if (c == ']' && stack.peek() != '[') return false;
stack.pop();
}
}

return stack.isEmpty();
}

Solution: Use stack to match brackets. Time: O(n), Space: O(n)

19. Min Stack

Problem: Design stack that supports push, pop, top, and getMin operations.
 class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;

public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}

public void push(int val) {

stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}

public void pop() {

if (!stack.isEmpty()) {
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
stack.pop();
}
}

public int top() {

return stack.peek();
}

public int getMin() {

return minStack.peek();
}
}

Solution: Use two stacks - one for values, one for minimums. Time: O(1), Space: O(n)

20. Evaluate Reverse Polish Notation

Problem: Evaluate expression in Reverse Polish Notation.

public int evalRPN(String[] tokens) {

Stack<Integer> stack = new Stack<>();

for (String token : tokens) {

if (token.equals("+")) {
stack.push(stack.pop() + stack.pop());
} else if (token.equals("-")) {
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
} else if (token.equals("*")) {
stack.push(stack.pop() * stack.pop());
} else if (token.equals("/")) {
int b = stack.pop();
int a = stack.pop();
stack.push(a / b);
} else {
stack.push(Integer.parseInt(token));
}
}

return stack.pop();
}

Solution: Use stack for operands. Time: O(n), Space: O(n)

21. Generate Parentheses

Problem: Generate all valid parentheses combinations.

public List<String> generateParenthesis(int n) {

List<String> result = new ArrayList<>();
backtrack(result, "", 0, 0, n);
return result;
}

private void backtrack(List<String> result, String current, int open, int close, int max) {
if (current.length() == max * 2) {
result.add(current);
return;
}

if (open < max) {

backtrack(result, current + "(", open + 1, close, max);
}
if (close < open) {
backtrack(result, current + ")", open, close + 1, max);
}
}

Solution: Backtracking with open/close count. Time: O(4^n/√n), Space: O(n)

[Previous sections remain the same...]

Stack (Continued)

22. Daily Temperatures

Problem: Find number of days to wait for a warmer temperature.

public int[] dailyTemperatures(int[] temperatures) {

int n = temperatures.length;
int[] result = new int[n];
Stack<Integer> stack = new Stack<>();

for (int i = 0; i < n; i++) {

while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prev = stack.pop();
result[prev] = i - prev;
}
stack.push(i);
}

return result;
}

Solution: Monotonic stack. Time: O(n), Space: O(n)

23. Car Fleet

Problem: Determine number of car fleets reaching destination.

 public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
double[][] cars = new double[n][2];
for (int i = 0; i < n; i++) {
cars[i] = new double[] {position[i], (double)(target - position[i]) / speed[i]};
}
Arrays.sort(cars, (a, b) -> Double.compare(a[0], b[0]));

int fleets = 0;
double slowest = 0;
for (int i = n - 1; i >= 0; i--) {
if (cars[i][1] > slowest) {
slowest = cars[i][1];
fleets++;
}
}

return fleets;
}

Solution: Sort by position, compare arrival times. Time: O(n log n), Space: O(n)

Binary Search

24. Binary Search

Problem: Find target in sorted array.

public int search(int[] nums, int target) {

int left = 0, right = nums.length - 1;

while (left <= right) {

int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}

return -1;
}

Solution: Classic binary search. Time: O(log n), Space: O(1)

25. Search a 2D Matrix

Problem: Search for target in sorted 2D matrix.

 public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) return false;

int m = matrix.length;
int n = matrix[0].length;
int left = 0;
int right = m * n - 1;

while (left <= right) {

int mid = left + (right - left) / 2;
int value = matrix[mid / n][mid % n];

if (value == target) {
return true;
} else if (value < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}

return false;
}

Solution: Treat 2D matrix as 1D array. Time: O(log(m*n)), Space: O(1)

26. Koko Eating Bananas

Problem: Find minimum eating speed to eat all bananas within h hours.

public int minEatingSpeed(int[] piles, int h) {

int left = 1;
int right = Arrays.stream(piles).max().getAsInt();

while (left < right) {

int mid = left + (right - left) / 2;
if (canEatAll(piles, mid, h)) {
right = mid;
} else {
left = mid + 1;
}
}

return left;
}

private boolean canEatAll(int[] piles, int k, int h) {

int hours = 0;
for (int pile : piles) {
hours += (pile + k - 1) / k;
}
return hours <= h;
}

Solution: Binary search on answer. Time: O(n * log(max)), Space: O(1)

27. Find Minimum in Rotated Sorted Array

Problem: Find minimum element in rotated sorted array.

 public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;

while (left < right) {

int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}

return nums[left];
}

Solution: Binary search with rotated array logic. Time: O(log n), Space: O(1)

28. Search in Rotated Sorted Array

Problem: Search for target in rotated sorted array.

public int search(int[] nums, int target) {

int left = 0;
int right = nums.length - 1;

while (left <= right) {

int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}

if (nums[left] <= nums[mid]) {

if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}

return -1;
}

Solution: Binary search with pivot handling. Time: O(log n), Space: O(1)

[Previous sections remain the same...]

Binary Search (Continued)

29. Time Based Key-Value Store

Problem: Design time-based key-value store with get/set operations.

 class TimeMap {
class Value {
String value;
int timestamp;
Value(String value, int timestamp) {
this.value = value;
this.timestamp = timestamp;
}
}

Map<String, List<Value>> map;

public TimeMap() {
map = new HashMap<>();
}

public void set(String key, String value, int timestamp) {

map.computeIfAbsent(key, k -> new ArrayList<>())
.add(new Value(value, timestamp));
}

public String get(String key, int timestamp) {

if (!map.containsKey(key)) return "";
List<Value> values = map.get(key);
return binarySearch(values, timestamp);
}

private String binarySearch(List<Value> values, int timestamp) {

int left = 0, right = values.size() - 1;
if (values.get(left).timestamp > timestamp) return "";
if (values.get(right).timestamp <= timestamp) return values.get(right).value;

while (left < right) {

int mid = left + (right - left + 1) / 2;
if (values.get(mid).timestamp <= timestamp) {
left = mid;
} else {
right = mid - 1;
}
}
return values.get(left).value;
}
}

Solution: HashMap with sorted lists and binary search. Time: O(log n) for get, O(1) for set. Space: O(n)

Linked List

30. Reverse Linked List

Problem: Reverse a singly linked list.

 public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;

while (curr != null) {

ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}

return prev;
}

Solution: Iterative with three pointers. Time: O(n), Space: O(1)

31. Merge Two Sorted Lists

Problem: Merge two sorted linked lists.

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

ListNode dummy = new ListNode(0);
ListNode curr = dummy;

while (l1 != null && l2 != null) {

if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}

curr.next = l1 != null ? l1 : l2;

return dummy.next;
}

Solution: Dummy node and two pointers. Time: O(n + m), Space: O(1)

32. Reorder List

Problem: Reorder list L0→Ln→L1→Ln-1→L2→Ln-2→...

 public void reorderList(ListNode head) {
if (head == null || head.next == null) return;

// Find middle
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

// Reverse second half

ListNode prev = null, curr = slow.next;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
slow.next = null;

// Merge two halves

ListNode first = head, second = prev;
while (second != null) {
ListNode next1 = first.next;
ListNode next2 = second.next;
first.next = second;
second.next = next1;
first = next1;
second = next2;
}
}

Solution: Find middle + reverse second half + merge. Time: O(n), Space: O(1)

33. Remove Nth Node From End of List

Problem: Remove nth node from end of list.

public ListNode removeNthFromEnd(ListNode head, int n) {

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;

// Advance first pointer by n+1 steps

for (int i = 0; i <= n; i++) {
first = first.next;
}

// Move both pointers until first reaches end

while (first != null) {
first = first.next;
second = second.next;
}

second.next = second.next.next;
return dummy.next;
}

Solution: Two pointers n-apart. Time: O(n), Space: O(1)

34. Copy List with Random Pointer

Problem: Deep copy linked list with random pointers.

 public Node copyRandomList(Node head) {
if (head == null) return null;

// Create interleaved copy

Node curr = head;
while (curr != null) {
Node copy = new Node(curr.val);
copy.next = curr.next;
curr.next = copy;
curr = copy.next;
}

// Set random pointers for copies

curr = head;
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}

// Separate original and copy lists

curr = head;
Node copyHead = head.next;
Node copyCurr = copyHead;
while (copyCurr.next != null) {
curr.next = curr.next.next;
copyCurr.next = copyCurr.next.next;
curr = curr.next;
copyCurr = copyCurr.next;
}
curr.next = null;

return copyHead;
}

Solution: Interleaved list approach. Time: O(n), Space: O(1)