Google Interview Question — LeetCode 1438

In this post, we are going to discuss the leetcode problem no. 1438 — Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit, which is recently asked in Google interviews.

Problem Analysis

This question is to find the maximum subarray, which the difference between the largest number and smallest number is within the given limit.

My Thinking Process

Usually, for questions to find the maximum subarray in a given array, the approach would be using a sliding window (or two pointers, which is the same thing). This also applies to this question.

Since this question asks us to get the maximum subarray with a limitation on the max and min values in the subarray, we can use a sliding window and keep track of the max values and min values in the window. So the logic is below:

1. Keep a sliding window with left point indexed at i and right point indexed at j.
2. Keep a queue minQ which tracks the minimum values in the sliding window; and a queue maxQ which tracks the maximum values in the sliding window.
3. If the current difference is within the limit, we can safely increment the right point.
4. If the current difference is beyond the limit, we can…