Daily Coding Day One Ninety One

, ,

According to the ~~~latest~~~three or four days back email gracing my inbox this question was asked by Google. Most of these questions are seemingly brain flexes with limited real world applicability, this one strikes me as somehow a bit more aligned to applicable than not, but still it’s thought excersi-y. It reminds me of some of the university work we would do in Java. I can’t stand Java though so implemented in JS.

Given an array of elements, return the length of the longest subarray where all its elements are distinct.

For example, given the array [5, 1, 3, 5, 2, 3, 4, 1], return 5 as the longest subarray of distinct elements is [5, 2, 3, 4, 1]

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
27
28
29
30
function longestSub(arr) {
    let maxLength = 0; 
    let left = 0; 
    const lastSeen = new Map(); 

    for (let right = 0; right < arr.length; right++) {
        const current = arr[right];

        // if current element is in the map and it's index is within the current window
        if (lastSeen.has(current) && lastSeen.get(current) >= left) {
            // slide to the right
            left = lastSeen.get(current) + 1;  
        }

        // update the index
        lastSeen.set(current, right);

        // get the new max length
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

// Test cases
console.log(lengthOfLongestSubarrayDistinct([5, 1, 3, 5, 2, 3, 4, 1]));  // Output: 5
console.log(lengthOfLongestSubarrayDistinct([1, 2, 3, 4, 5]));  // Output: 5
console.log(lengthOfLongestSubarrayDistinct([1, 2, 2, 3, 4, 4]));  // Output: 3
console.log(lengthOfLongestSubarrayDistinct([]));  // Output: 0