Problem statement

/

Solution 1

In fact, quite difficult problem, O(n) time complexity solution is more difficult that some of the other hard problems. First solution is to use sliding window, when the min is too small increment the left pointer and when we have a valid subarray we move the right pointer.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        n = len(nums)
        SList = SortedList()
        lft, rgh, ans = 0, 0, 0
        while rgh < n:
            while rgh < n and (not SList or SList[0] * 2 > SList[-1]):
                SList.add(nums[rgh])
                rgh += 1
                if SList[0] * 2 > SList[-1]: ans = max(ans, rgh - lft)
            while lft < rgh and SList and SList[0] * 2 <= SList[-1]:
                SList.remove(nums[lft])
                lft += 1
                if SList and SList[0] * 2 > SList[-1]: ans = max(ans, rgh - lft)

        return ans

Solution 2

Another solution is to use monotonic deques: one where we have not-decreasing values and another where we have not-increasing values. Also we again use two pointers approach, where we extend our window to the right and shrink to the left.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        minq, maxq = deque(), deque()
        l, r, ans = 0, 0, 0
        while r < len(nums):
            x = nums[r]
            while minq and x < nums[minq[-1]]: minq.pop()
            minq.append(r)
            while maxq and x > nums[maxq[-1]]: maxq.pop()
            maxq.append(r)
            r += 1
            while l < r and nums[minq[0]] * 2 <= nums[maxq[0]]:
                if minq[0] == l: minq.popleft()
                if maxq[0] == l: maxq.popleft()
                l += 1
            ans = max(ans, r - l)
        return ans