Window Limits - Google Top Interview Questions


Problem Statement :


You are given a list of integers nums and integers window and limit. 

Return whether abs(nums[i] - nums[j]) ≤ limit for every i, j such that abs(i - j) < window.

Constraints

1 ≤ n ≤ 100,000 where n is the length of nums

1 ≤ window ≤ n

0 ≤ limit < 2 ** 31

Example 1

Input

nums = [1, 3, 7, 5]

window = 2

limit = 4

Output

True

Explanation

Every number within a window of size 2 has pair differences of at most 4 (from 3 and 7).



Example 2

Input

nums = [1, 3, 7, 5]

window = 3

limit = 4

Output

False

Explanation

Within a window size of 3 we have abs(1 - 7) > 4, so this is above the limit.


Solution :



title-img 




                        Solution in C++ :

bool solve(vector<int>& nums, int window, int limit) {
    multiset<long long> dp;
    for (int i = 0; i < nums.size(); i++) {
        dp.insert(nums[i]);
        if (i >= window) dp.erase(dp.find(nums[i - window]));
        if (*dp.rbegin() - *dp.begin() > limit) return false;
    }
    return true;
}
                    


                        Solution in Java :

import java.util.*;

class Solution {
    public boolean solve(int[] nums, int window, int limit) {
        Deque<Integer> q = new ArrayDeque();
        Deque<Integer> q2 = new ArrayDeque();
        int r = 0;
        while (r < nums.length) {
            while (!q.isEmpty() && q.peekFirst() <= r - window) {
                q.removeFirst();
            }
            while (!q2.isEmpty() && q2.peekFirst() <= r - window) {
                q2.removeFirst();
            }
            while (!q.isEmpty() && nums[q.peekLast()] < nums[r]) {
                q.removeLast();
            }
            while (!q2.isEmpty() && nums[q2.peekLast()] > nums[r]) {
                q2.removeLast();
            }
            q.offerLast(r);
            q2.offerLast(r++);
            int max = nums[q.peekFirst()];
            int min = nums[q2.peekFirst()];
            if (max - min > limit) {
                return false;
            }
        }
        return true;
    }
}
                    


                        Solution in Python : 
                            
class Solution:
    def solve(self, nums, window, limit):
        minq = deque()  # <idx, val>
        maxq = deque()  # <idx, val>
        for i, x in enumerate(nums):
            while minq and minq[-1][1] >= x:
                minq.pop()
            while maxq and maxq[-1][1] <= x:
                maxq.pop()
            minq.append((i, x))
            maxq.append((i, x))
            if minq[0][0] <= i - window:
                minq.popleft()
            if maxq[0][0] <= i - window:
                maxq.popleft()
            if maxq[0][1] - minq[0][1] > limit:
                return False
        return True


View More Similar Problems

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →

Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →

Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →

Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →

Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →