Why do i get an infinite loop when I use int instead of Integer in Java?

Question

I am trying to solve the problem 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit. I got the logic but there was a very weird problem due to which I had to pull my hair for more than two hours.

Here is the code :-

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxDeque = new LinkedList();
        Deque<Integer> minDeque = new LinkedList();
        Queue<Integer> queue = new LinkedList();

        int maxLength = 1;

        for (int i = 0; i < nums.length; i++) {
            Integer temp = nums[i];
            //int temp = nums[i]; //If I uncomment this line and comment the above line, the code does not work.
            queue.offer(temp);

            while (!maxDeque.isEmpty() && maxDeque.peekLast() < temp) {
                maxDeque.removeLast();
            }

            while (!minDeque.isEmpty() && minDeque.peekLast() > temp) {
                minDeque.removeLast();
            }

            maxDeque.offerLast(temp);
            minDeque.offerLast(temp);

            while (maxDeque.peekFirst() - minDeque.peekFirst() > limit) {
                if (queue.peek() == maxDeque.peekFirst()) {
                    maxDeque.pollFirst();
                }

                if (queue.peek() == minDeque.peekFirst()) {
                    minDeque.pollFirst();
                }

                queue.poll();
            }

            
            maxLength = Math.max(maxLength, queue.size());

        }

        return maxLength;
    }
}

You see when I put an integer into each of the queues, the code runs fine but when I put an int into the three queues, I get a TLE. So, in the below code, if temp is Integer, the code passes but when temp is int, it gives a TLE. Can someone please explain what is going on ?

The `int` version does an extra 2 boxing operations per iteration, but I wouldn't expect it to have such an impact. — shmosel, May 31 '22 at 16:03
I would expect an NPE to be thrown (and not swallowed elsewheres), but to double check: there are no values within `nums` that are `null`, correct? (Verify this in the code itself, not just by assumption) — Rogue, May 31 '22 at 16:05
No. I checked the values are not null. You can verify yourself by running the code in the leetcode IDE. — Abascus, May 31 '22 at 16:10

score 2 · Accepted Answer · answered May 31 '22 at 16:09

2

Don't use == to compare Integers. It only works when you pre-box temp because of reference equality. Use .equals() instead:

if (queue.peek().equals(maxDeque.peekFirst())) {
    maxDeque.pollFirst();
}

if (queue.peek().equals(minDeque.peekFirst())) {
    minDeque.pollFirst();
}

answered May 31 '22 at 16:09

shmosel

49,289
6
73
138

That's a good catch! I think it should only work for small numbers, because of interning: https://stackoverflow.com/questions/5277881/why-arent-integers-cached-in-java – GeertPt May 31 '22 at 16:23

Why do i get an infinite loop when I use int instead of Integer in Java?

1 Answers1