Contiguous Score Range — Problem Statement & Solution Guide

Two PointersMediumSliding Window / Ordered Map

TimeO(n)

SpaceO(u)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Two Pointers and solve the Contiguous Score Range problem optimally.

TopicTwo Pointers

PatternSliding Window / Ordered Map

TimeO(n)

SpaceO(u)

Problem Description

Given an integer array scores, determine the maximum length of a contiguous subarray in which the absolute difference between the smallest and the largest element does not exceed 1. The subarray must consist of consecutive positions from the original array. Return the length of the longest such subarray. If no subarray satisfies the condition, return 0 (the empty subarray).

DSA Pattern Breakdown

"Contiguous Score Range"

medium

WHY DOES IT MATTER?

Sliding‑window patterns are fundamental for any problem that asks for the longest/shortest subarray meeting a monotonic constraint, because they turn global recomputation into local updates.

OPTIMIZATION CHALLENGE

The key insight is that the window’s validity depends only on its current min and max, not on the entire ordering, so we can maintain these extremes incrementally with a frequency map, avoiding recomputation for each shift.

REAL-WORLD CONNECTION

Think of a network traffic monitor that keeps a rolling window of packet sizes; it must raise an alert only when the size spread exceeds a threshold, continuously sliding as new packets arrive, just like the algorithm slides the window over scores.

During an interview, first state the invariant (|max‑min|≤1) and then describe how you’ll expand right, update counts, and only move left enough to restore the invariant—this shows you understand amortized analysis.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(u)

Core Theory — Why This Approach?

The problem asks for the longest contiguous subarray where the max‑min difference is at most one. A naive scan that recomputes min and max for every possible window leads to O(n^2) time because each extension requires a full scan of the window. The optimal solution leverages the two‑pointer (sliding window) technique combined with a frequency map (or balanced BST) to maintain the current window’s minimum and maximum in O(1) amortized time. As the right pointer expands, we update the counts of the incoming element; if the window violates the |max‑min|≤1 condition, we shrink the left pointer while decrementing counts until the constraint is restored. This guarantees each element is visited at most twice, yielding linear time. The approach exemplifies how maintaining incremental state eliminates repeated work, turning an otherwise quadratic enumeration into a linear scan suitable for large inputs (up to 10^5 or more).

Interview Questions on This Problem

Q1How would you modify the sliding‑window solution if the allowed difference between max and min were a variable K instead of 1?

Keep the same two‑pointer framework but replace the constant check with |max‑min|≤K; the frequency map (or multiset) still provides current min and max in O(1) or O(log U) time, so the overall complexity remains O(n).

Q2Why does a simple “reset when difference >1” strategy fail for inputs like [1,2,2,3,2]?

Resetting discards useful prefix information; the window can still be valid after dropping only the leftmost element(s). The two‑pointer method shrinks minimally, preserving longer windows that a full reset would miss.

Examples

Example 1

Input

[4,5,5,6,7,6,5]

Output

Explanation: The subarray [5,5,6] (indices 1‑3) has min=5, max=6, diff=1, length=3. No longer contiguous segment keeps the difference ≤1, so the answer is 3.

Example 2

Input

[1,2,2,2,3,4,4,5]

Output

Explanation: The segment [1,2,2,2] (indices 0‑3) and also [2,2,2,3] (indices 1‑4) both have min and max differing by 1 and length 4, which is maximal.

Example 3

Input

[9,9,9,9]

Output

Explanation: All elements are equal, so the whole array satisfies the condition, giving length 4.

Constraints

1 <= scores.length <= 100000
-1000000000 <= scores[i] <= 1000000000
Solution must run in O(n) time using O(k) additional space where k is the number of distinct values in the current window

Optimal Approach & Strategy

Use a sliding window with a frequency map to keep current min and max, moving the left pointer only when the constraint is violated; this yields O(n) time.

Brute Force Approach

Check every possible subarray, compute its min and max, and keep the longest that satisfies the condition; this is O(n^2).

Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
function maxContiguousScoreRange(scores){
    const n = scores.length;
    let left = 0, ans = 0;
    const minDeque = [];
    const maxDeque = [];
    const push = (deque, val, isMin) => {
        while(deque.length && (isMin ? deque[deque.length-1] > val : deque[deque.length-1] < val)) deque.pop();
        deque.push(val);
    };
    const pop = (deque, val) => {
        if(deque.length && deque[0] === val) deque.shift();
    };
    for(let right=0; right<n; ++right){
        const v = scores[right];
        push(minDeque, v, true);
        push(maxDeque, v, false);
        while(maxDeque[0] - minDeque[0] > 1){
            const rem = scores[left];
            pop(minDeque, rem);
            pop(maxDeque, rem);
            ++left;
        }
        ans = Math.max(ans, right-left+1);
    }
    return ans;
}
if(input.length===0){process.exit(0);} 
const n = input[idx++];
const scores = input.slice(idx, idx+n);
console.log(maxContiguousScoreRange(scores));

#include <bits/stdc++.h>
using namespace std;
int maxContiguousScoreRange(const vector<int>& scores){
    int n=scores.size();
    int left=0, ans=0;
    map<int,int> cnt;
    for(int right=0; right<n; ++right){
        cnt[scores[right]]++;
        while(!cnt.empty() && cnt.rbegin()->first - cnt.begin()->first > 1){
            int val=scores[left];
            if(--cnt[val]==0) cnt.erase(val);
            ++left;
        }
        ans = max(ans, right-left+1);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> scores(n);
    for(int i=0;i<n;++i) cin>>scores[i];
    cout<<maxContiguousScoreRange(scores);
    return 0;
}

import java.util.*;
public class Main {
    static int maxContiguousScoreRange(int[] scores){
        int n = scores.length;
        int left = 0, ans = 0;
        Deque<Integer> minDeque = new ArrayDeque<>();
        Deque<Integer> maxDeque = new ArrayDeque<>();
        for(int right=0; right<n; ++right){
            int v = scores[right];
            while(!minDeque.isEmpty() && minDeque.peekLast() > v) minDeque.pollLast();
            minDeque.addLast(v);
            while(!maxDeque.isEmpty() && maxDeque.peekLast() < v) maxDeque.pollLast();
            maxDeque.addLast(v);
            while(maxDeque.peekFirst() - minDeque.peekFirst() > 1){
                int rem = scores[left];
                if(minDeque.peekFirst() == rem) minDeque.pollFirst();
                if(maxDeque.peekFirst() == rem) maxDeque.pollFirst();
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        if(!sc.hasNextInt()) return;
        int n = sc.nextInt();
        int[] scores = new int[n];
        for(int i=0;i<n;i++) scores[i]=sc.nextInt();
        System.out.println(maxContiguousScoreRange(scores));
    }
}

from collections import deque

def max_contiguous_score_range(scores):
    n=len(scores)
    left=0
    ans=0
    min_d=deque()
    max_d=deque()
    for right,v in enumerate(scores):
        while min_d and min_d[-1]>v:
            min_d.pop()
        min_d.append(v)
        while max_d and max_d[-1]<v:
            max_d.pop()
        max_d.append(v)
        while max_d[0]-min_d[0]>1:
            rem=scores[left]
            if min_d[0]==rem:
                min_d.popleft()
            if max_d[0]==rem:
                max_d.popleft()
            left+=1
        ans=max(ans,right-left+1)
    return ans

if __name__=="__main__":
    import sys, ast
    data=sys.stdin.read().strip()
    if not data:
        sys.exit(0)
    scores=ast.literal_eval(data)
    print(max_contiguous_score_range(scores))

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
function maxContiguousScoreRange(scores){
    const n = scores.length;
    let left = 0, ans = 0;
    const minDeque = [];
    const maxDeque = [];
    const push = (deque, val, isMin) => {
        while(deque.length && (isMin ? deque[deque.length-1] > val : deque[deque.length-1] < val)) deque.pop();
        deque.push(val);
    };
    const pop = (deque, val) => {
        if(deque.length && deque[0] === val) deque.shift();
    };
    for(let right=0; right<n; ++right){
        const v = scores[right];
        push(minDeque, v, true);
        push(maxDeque, v, false);
        while(maxDeque[0] - minDeque[0] > 1){
            const rem = scores[left];
            pop(minDeque, rem);
            pop(maxDeque, rem);
            ++left;
        }
        ans = Math.max(ans, right-left+1);
    }
    return ans;
}
if(input.length===0){process.exit(0);} 
const n = input[idx++];
const scores = input.slice(idx, idx+n);
console.log(maxContiguousScoreRange(scores));

Asked in Top Tech Interviews

UberRazorpay

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.