CODEWITHSUNDEEP
javaalgorithmarray-algorithms
user16037629
user16037629

Reputation:

Why does the method not compute maximum greater than 65537?

public int longestConsecutive(int[] nums) {
        Map<Integer, Boolean> numMap = new ConcurrentHashMap<>();
        Map<Integer, Integer> maxMap = new ConcurrentHashMap<>();
        for (int i : nums) {
            numMap.put(i, false);
        }
        int max = 0;
        for (int n : numMap.keySet()) {
            numMap.remove(n);

            if (maxMap.containsKey(n - 1)) {
                maxMap.put(n, maxMap.get(n - 1) + 1);
                max = Math.max(maxMap.get(n), max);
                continue;
            }

            int lessThan = 0;
            while (numMap.containsKey(n - lessThan - 1)) {
                numMap.remove(n - 1);
                lessThan++;
            }
            maxMap.put(n, lessThan + 1);
            if (lessThan + 1 > max) {
                max = lessThan + 1;
            }

        }
        return max;
    }

This is my solution to Longest Consecutive Sequence problem and it works for all but 1 of the 70 cases. The 70th case array has length 100,000. I checked my solution for this and other lengths of the array and I observed that the max value returned is always 65537 for arrays of size greater than 65537. I can't seem to figure out why that is the case. I wonder if it has something to do with using ConcurrentHashmap.

Here's my test:

  @Test
    public void test() {

        for (int i = 0; i < 100000; i++) {
            int n = i;
            int[] arr = new int[n];
            for (int j = 0; j < n; j++) {
                arr[j] = j;
            }
            assertEquals(n, longestConsecutive(arr));
        }

    }

The test fails at 65538 by returning 65537. And I also checked for some random values greater than that and it failed for them too with the same value.

Upvotes: 1

Views: 149

Answers (1)

DuncG
DuncG

Reputation: 15186

ConcurrentModificationException means your logic is wrong - you are editing and iterating a map at the same time.

The iteration numMap.keySet() is the values of nums - you should be OK to change the outer loop to:

for (int n : nums) {
    ...
}

This avoids ConcurrentModificationException on the iterator while edits are performed. You don't need to use ConcurrentHashMap over HashMap - both should work fine in this situation, and the tests pass for 100,000.

Upvotes: 2

Related Questions