Hash Map Techniques

LeetCode 1: Two Sum

Utilize a hash map to store elements not yet encountered, while searching for the complement target - nums[i].

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

LeetCode 49: Group Anagrams

Group anagrams by sorting characters in each string and using the sorted version as a key in a map.

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> result = new ArrayList<>();
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
    }
    result.addAll(map.values());
    return result;
}

LeetCode 128: Longest Consecutive Sequence

Use a set to store all numbers, then find sequences starting from numbers that have no predecessor.

public int longestConsecutive(int[] nums) {
    Set<Integer> numSet = new HashSet<>();
    for (int num : nums) numSet.add(num);
    int maxLength = 0;
    for (int num : numSet) {
        if (!numSet.contains(num - 1)) {
            int currentNum = num;
            int currentLength = 1;
            while (numSet.contains(currentNum + 1)) {
                currentNum++;
                currentLength++;
            }
            maxLength = Math.max(maxLength, currentLength);
        }
    }
    return maxLength;
}

Two Pointers

LeetCode 283: Move Zeroes

Apply a two-pointer technique similar to removing elements, where one pointer tracks non-zero elements and another fills zeros at the end.

public void moveZeroes(int[] nums) {
    int writeIndex = 0;
    for (int readIndex = 0; readIndex < nums.length; readIndex++) {
        if (nums[readIndex] != 0) {
            nums[writeIndex++] = nums[readIndex];
        }
    }
    while (writeIndex < nums.length) {
        nums[writeIndex++] = 0;
    }
}

LeetCode 11: Container With Most Water

Use two pointers to calculate maximum area formed between vertical lines.

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

LeetCode 15: Three Sum

Sort the array and use a two-pointer approach to avoid duplicates and efficiently search triplets.

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) break;
        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) left++;
            else if (sum > 0) right--;
            else {
                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--;
            }
        }
    }
    return result;
}

LeetCode 42: Trapping Rain Water

Caluclate trapped water by comparing heights from both ends, keeping track of maximum boundaries.

public int trap(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int leftMax = 0;
    int rightMax = 0;
    int totalWater = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                totalWater += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                totalWater += rightMax - height[right];
            }
            right--;
        }
    }
    return totalWater;
}

Sliding Window

LeetCode 3: Longest Substring Without Repeating Characters

Track character positions using a map to adjust window bonudaries dynamical.

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charIndex = new HashMap<>();
    int maxLength = 0;
    int start = 0;
    for (int end = 0; end < s.length(); end++) {
        char ch = s.charAt(end);
        if (charIndex.containsKey(ch)) {
            start = Math.max(start, charIndex.get(ch) + 1);
        }
        charIndex.put(ch, end);
        maxLength = Math.max(maxLength, end - start + 1);
    }
    return maxLength;
}

LeetCode 438: Find All Anagrams in a String

Use sliding window with frequency arrays to detect anagram matches.

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s.length() < p.length()) return result;
    
    int[] pFreq = new int[26];
    int[] sFreq = new int[26];
    
    for (int i = 0; i < p.length(); i++) {
        pFreq[p.charAt(i) - 'a']++;
        sFreq[s.charAt(i) - 'a']++;
    }
    
    if (Arrays.equals(pFreq, sFreq)) result.add(0);
    
    for (int i = 0; i < s.length() - p.length(); i++) {
        sFreq[s.charAt(i) - 'a']--;
        sFreq[s.charAt(i + p.length()) - 'a']++;
        if (Arrays.equals(pFreq, sFreq)) result.add(i + 1);
    }
    return result;
}

Subarray Problems

LeetCode 560: Subarray Sum Equals K

Use prefix sums along with a hash map to efficiently count subarrays with target sum.

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixSumCount = new HashMap<>();
    prefixSumCount.put(0, 1);
    int sum = 0;
    int count = 0;
    for (int num : nums) {
        sum += num;
        if (prefixSumCount.containsKey(sum - k)) {
            count += prefixSumCount.get(sum - k);
        }
        prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0) + 1);
    }
    return count;
}

LeetCode 239: Sliding Window Maximum

Maintain a monotonic decreasing deque to quickly access maximum values within sliding windows.

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    int[] result = new int[nums.length - k + 1];
    int index = 0;
    
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        if (i >= k - 1) {
            result[index++] = nums[deque.peekFirst()];
        }
    }
    return result;
}

LeetCode 76: Minimum Window Substring

Apply sliding window with character frequency maps to find minimal covering substring.

public String minWindow(String s, String t) {
    Map<Character, Integer> required = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    
    for (char c : t.toCharArray()) {
        required.put(c, required.getOrDefault(c, 0) + 1);
    }
    
    int left = 0;
    int right = 0;
    int formedChars = 0;
    int requiredChars = required.size();
    int minLen = Integer.MAX_VALUE;
    int[] result = {-1, 0, 0};
    
    while (right < s.length()) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        
        if (required.containsKey(c) && window.get(c).equals(required.get(c))) {
            formedChars++;
        }
        
        while (left <= right && formedChars == requiredChars) {
            c = s.charAt(left);
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                result[0] = left;
                result[1] = right;
            }
            
            window.put(c, window.get(c) - 1);
            if (required.containsKey(c) && window.get(c) < required.get(c)) {
                formedChars--;
            }
            left++;
        }
        right++;
    }
    
    return minLen == Integer.MAX_VALUE ? "" : s.substring(result[0], result[1] + 1);
}

General Array Operations

LeetCode 53: Maximum Subarray

Implement dynamic programming to compute maximum contiguous subarray sum.

public int maxSubArray(int[] nums) {
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];
    for (int i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

LeetCode 56: Merge Intervals

Sort intervals and merge overlapping ones based on boundary comparisons.

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> merged = new ArrayList<>();
    
    for (int[] interval : intervals) {
        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
            merged.add(interval);
        } else {
            merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
        }
    }
    return merged.toArray(new int[merged.size()][]);
}

LeetCode 189: Rotate Array

Reverse segments of the array to achieve rotation effect in O(1) space.

public void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n;
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

LeetCode 238: Product of Array Except Self

Calculate left and right products separately using two passes.

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] leftProducts = new int[n];
    int[] rightProducts = new int[n];
    int[] result = new int[n];
    
    leftProducts[0] = 1;
    for (int i = 1; i < n; i++) {
        leftProducts[i] = leftProducts[i - 1] * nums[i - 1];
    }
    
    rightProducts[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--) {
        rightProducts[i] = rightProducts[i + 1] * nums[i + 1];
    }
    
    for (int i = 0; i < n; i++) {
        result[i] = leftProducts[i] * rightProducts[i];
    }
    return result;
}

LeetCode 41: First Missing Positive

Sort the array and iterate through it to find the first missing positive integer.

public int firstMissingPositive(int[] nums) {
    Arrays.sort(nums);
    int expected = 1;
    for (int num : nums) {
        if (num > expected) {
            return expected;
        }
        expected = Math.max(expected, num + 1);
    }
    return expected;
}