SvenStack

🧩 Problem Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4]. Therefore its length is 4.

💡 Brute Force? Not Enough

A naive solution would be to:

• Sort the array → O(n log n)
• Iterate to find longest streak

This fails the O(n) constraint, so we need a better approach.

💡 Optimized Approach (Using HashSet)

To achieve linear time:

1. Store all numbers in a HashSet for constant-time lookups.
2. Iterate through the array, and only start a new sequence if num - 1 is not in the set (i.e., it’s the start of a sequence).
3. Expand forward: check how long the consecutive streak goes.
4. Track the max length.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

        int maxLen = 0;

        for (int num : nums) {
            if (!set.contains(num - 1)) {
                int current = num;
                int length = 1;

                while (set.contains(current + 1)) {
                    current++;
                    length++;
                }

                maxLen = Math.max(maxLen, length);
            }
        }

        return maxLen;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Each number is added and checked in constant time.
• Space Complexity: O(n)
  To store all unique numbers in the HashSet.

✍️ Summary

• This is a great example of using HashSet to eliminate redundant computation.
• The key optimization is only starting a streak when num - 1 is not in the set.
• Sorting is too slow for this problem — always check time constraints carefully.

This technique of using hash-based lookup to replace sorting is common in many “O(n)” constraint problems.

🧩 Problem Description

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all original letters exactly once.

Example:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

💡 Approach

🔸 Idea

Two strings are anagrams if their sorted character arrays are the same.

So we can:

• Sort each string.
• Use a hash map to group original strings by their sorted version.

🔧 Why Hash Table?

The sorted string acts as a unique key for anagram groups.
We use a Map<String, List<String>> to group anagrams efficiently.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import java.util.*;

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

        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars); // sorted string

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

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

⏱ Time and Space Complexity

• Time Complexity: O(n * k log k)
  • n = number of strings
  • k = max length of a string (due to sorting)
• Space Complexity: O(n * k)
  • To store grouped anagrams in a hash map

✍️ Summary

• Key idea: Use the sorted string as hash map key.
• Efficient and elegant hash table application.
• Classic grouping problem using Java Map and sorting.

🧩 Problem Description

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

💡 Naive Approach (Brute Force)

The most straightforward idea is to check all pairs using two nested loops.
This guarantees we find the solution, but it’s inefficient for large arrays.

🔢 Java Code – Brute Force

1
2
3
4
5
6
7
8
9
10
11
12

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[] {}; 
    }
}

⏱ Complexity

• Time Complexity: O(n²)
• Space Complexity: O(1)

⚠️ This solution does not scale — it fails performance constraints on large inputs.

💡 Optimized Approach (Hash Map)

To reduce time complexity, we use a hash map to store values we’ve seen and their indices.
While iterating, we check whether target - current has already been seen.

🔎 Key Points

• In practice, hash tables are fast — usually O(1) for most operations.
• Worst case happens when many keys collide (bad hash function or high load factor).
• Java’s HashMap uses a red-black tree (Deeper explanation will be covered in a future post.) for long collision chains (O(log n) worst case for search).

🔢 Java Code – Hash Map

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // hashtable always 
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[] {seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        return new int[] {}; 
    }
}

⏱ Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

✅ Efficient and suitable for large datasets.

✍️ Summary

• Always start with brute force to validate your logic.
• Then optimize using data structures like hash maps.