- Two Sum
Given an array of integers nums and a target value target, find the indices of two numbers that add up to target. Return the indices as a pair.
Solution 1: Brute Force
class Solution {
public 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[0];
}
}
Solution 2: HashMap
class Solution {
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];
}
}
- Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. Each digit is stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + carry;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}
}
- Longest Substring Without Repeating Characters
Find the length of the longest substring without repeating characters.
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0, max = 0;
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
max = Math.max(max, right - left + 1);
}
return max;
}
}
- Container With Most Water
Given an array of heights, find two lines that together with the x-axis form a container that holds the most water.
class Solution {
public int maxArea(int[] height) {
int max = 0, left = 0, right = height.length - 1;
while (left < right) {
max = Math.max(max, (right - left) * Math.min(height[left], height[right]));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
}
}
- 3Sum
Find all unique triplets in the array which give the sum of zero.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
int left = i + 1, right = nums.length - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
res.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 < target) {
left++;
} else {
right--;
}
}
}
}
return res;
}
}
- Remove Nth Node From End of List
Remove the nth node from the end of a linked list and return its head.
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode fast = head, slow = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
- Merge Two Sorted Lists
Merge two sorted linked lists and reeturn it as a new sorted list.
class Solution {
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;
}
}
- Swap Nodes in Pairs
Swap every two adjacent nodes in a linked list without changing node values.
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode curr = dummy;
while (curr.next != null && curr.next.next != null) {
ListNode first = curr.next;
ListNode second = curr.next.next;
curr.next = second;
first.next = second.next;
second.next = first;
curr = first;
}
return dummy.next;
}
}
- Reverse Nodes in k-Group
Reverse the nodes of a linked list k at a time and return the modified list.
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count < k) {
curr = curr.next;
count++;
}
if (count == k) {
curr = reverseKGroup(curr, k);
while (count-- > 0) {
ListNode temp = head.next;
head.next = curr;
curr = head;
head = temp;
}
return curr;
}
return head;
}
}
- Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the position where it would be inserted.
class Solution {
public int searchInsert(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;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
}
- Trapping Rain Water
Compute how much water can be trapped after raining.
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int ans = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) leftMax = height[left];
else ans += leftMax - height[left];
left++;
} else {
if (height[right] >= rightMax) rightMax = height[right];
else ans += rightMax - height[right];
right--;
}
}
return ans;
}
}
- Group Anagrams
Group anagrams from a list of strings.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] arr = s.toCharArray();
Arrays.sort(arr);
String key = new String(arr);
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(s);
}
return new ArrayList<>(map.values());
}
}
- Climbing Stairs
How many distinct ways are there to climb to the top of a staircase where you can take 1 or 2 steps at a time?
class Solution {
public int climbStairs(int n) {
int a = 1, b = 1;
for (int i = 2; i <= n; i++) {
int temp = b;
b = a + b;
a = temp;
}
return b;
}
}
- Binary Tree Inorder Traversal
Return the inorder traversal of a binary tree's nodes' values.
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
private void helper(TreeNode node, List<Integer> res) {
if (node != null) {
helper(node.left, res);
res.add(node.val);
helper(node.right, res);
}
}
}
- Longest Consecutive Sequence
Find the length of the longest consecutive elements sequence in an unsorted array.
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) set.add(num);
int longest = 0;
for (int num : nums) {
if (!set.contains(num - 1)) {
int current = num;
int length = 1;
while (set.contains(current + 1)) {
current++;
length++;
}
longest = Math.max(longest, length);
}
}
return longest;
}
}
- Copy List with Random Pointer
Make a deep copy of a linked list with random pointers.
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
Map<Node, Node> map = new HashMap<>();
Node curr = head;
while (curr != null) {
map.put(curr, new Node(curr.val));
curr = curr.next;
}
curr = head;
while (curr != null) {
map.get(curr).next = map.get(curr.next);
map.get(curr).random = map.get(curr.random);
curr = curr.next;
}
return map.get(head);
}
}
- Linked List Cycle
Determine if a linked list has a cycle.
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
while (head != null) {
if (visited.contains(head)) return true;
visited.add(head);
head = head.next;
}
return false;
}
}
- Linked List Cycle II
Find the node where the cycle begins in a linked list.
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}
- Intersection of Two Linked Lists
Find the node at which the two linked lists intersect.
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = (pA != null) ? pA.next : headB;
pB = (pB != null) ? pB.next : headA;
}
return pA;
}
}
- Reverse Linked List
Reverse a singly linked list.
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
- Palindrome Linked List
Determine if a linked list is a palindrome.
class Solution {
private ListNode front;
public boolean isPalindrome(ListNode head) {
front = head;
return recursivelyCheck(head);
}
private boolean recursivelyCheck(ListNode currentNode) {
if (currentNode != null) {
if (!recursivelyCheck(currentNode.next)) return false;
if (currentNode.val != front.val) return false;
front = front.next;
}
return true;
}
}
- Move Zeroes
Move all zeroes to the end of the array while maintaining the relative order of non-zero elements.
class Solution {
public void moveZeroes(int[] nums) {
int lastNonZero = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[lastNonZero++] = nums[i];
}
}
for (int i = lastNonZero; i < nums.length; i++) {
nums[i] = 0;
}
}
}
- Find All Anagrams in a String
Find all the start indices of p's anagrams in s.
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s.length() < p.length()) return result;
int[] pCount = new int[26];
int[] sCount = new int[26];
for (char c : p.toCharArray()) pCount[c - 'a']++;
for (int i = 0; i < p.length(); i++) sCount[s.charAt(i) - 'a']++;
if (Arrays.equals(pCount, sCount)) result.add(0);
for (int i = 0; i < s.length() - p.length(); i++) {
sCount[s.charAt(i) - 'a']--;
sCount[s.charAt(i + p.length()) - 'a']++;
if (Arrays.equals(pCount, sCount)) result.add(i + 1);
}
return result;
}
}
- Subarray Sum Equals K
Find the number of contiguous subarrays whose sum equals k.
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixSumCount = new HashMap<>();
prefixSumCount.put(0, 1);
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
count += prefixSumCount.getOrDefault(sum - k, 0);
prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0) + 1);
}
return count;
}
}