Hashing

Longest Consecutive Sequence in an Array

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (var x : nums) {
            set.add(x);
        }
 
        int maxStreak = 0;
        for (var x : nums) {
            if (set.contains(x - 1)) continue;
 
            int currStreak = 1;
            while (set.contains(x + 1)) {
                ++currStreak;
                ++x;
            }
 
            maxStreak = Math.max(maxStreak, currStreak);
        }
 
        return maxStreak;
    }
}

The algorithm finds the longest sequence of consecutive numbers in an unsorted array. It begins by inserting all array elements into a hash set for quick access. Then, it iterates through each number, checking if it marks the beginning of a sequence (i.e., num - 1 is not in the set). If it is, the algorithm counts the length of the consecutive sequence starting from that number and updates the maximum length found.

Time Complexity: O(n), because although there are nested loops, each number is processed at most twice.

Space Complexity: O(n), for storing the numbers in the hash set.

Longest subarray with sum K

class Solution {
    public int longestSubarray(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
 
        int sum = 0;
        int res = 0;
        for (int i = 0;  i < nums.length; ++i) {
            sum += nums[i];
 
            if (map.containsKey(sum - k)) {
                res = Math.max(res, i - map.get(sum - k));
            }
 
            map.putIfAbsent(sum, i);
        }
 
        return res;
    }
}

This algorithm finds the length of the longest subarray that sums to a target k. It uses a hash map to store the first-seen index of each cumulative sum. While traversing the array, it checks if current_sum - k exists in the map. If it does, a subarray with sum k is found, and its length is calculated. The algorithm maintains the maximum length seen so far.

Time Complexity: O(n), as it iterates through the array once.

Space Complexity: O(n) in the worst case, to store all unique prefix sums.

Count subarrays with given sum

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
 
        int res = 0;
        int sum = 0;
        for (var x : nums) {
            sum += x;
 
            if (map.containsKey(sum - k)) {
                res += map.get(sum - k);
            }
 
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
 
        return res;
    }
}

This algorithm tallies the number of contiguous subarrays summing to k. It leverages a hash map to keep track of the frequencies of cumulative sums. As it traverses the array, it calculates the current prefix sum and checks if current_sum - k is present in the map. If it is, the count associated with that sum is added to the result, representing the number of subarrays ending at the current position that sum to k.

Time Complexity: O(n), due to a single pass through the array.

Space Complexity: O(n), as the map could potentially store all unique prefix sums.

Count subarrays with given xor K

class Solution {
    public int subarraysWithXorK(int[] nums, int k) {
        var map = new HashMap<Integer, Integer>();
        map.put(0, 1);
 
        int res = 0;
        int xor = 0;
        for (var x : nums) {
            xor ^= x;
 
            if (map.containsKey(xor ^ k)) {
                res += map.get(xor ^ k);
            }
 
            map.put(xor, map.getOrDefault(xor, 0) + 1);
        }
 
        return res;
    }
}

The algorithm counts subarrays with an XOR sum equal to k. It works by maintaining a running XOR prefix. Based on the property prefix_xor_j = prefix_xor_i ^ k, it uses a hash map to store frequencies of these XOR prefixes. For each element, it updates the running XOR and checks if a running_xor ^ k has been seen before, adding its frequency to the total count.

Time Complexity: O(n), from a single traversal of the array.

Space Complexity: O(n) in the worst case, for storing the XOR prefix frequencies in the map.