Task · algorithms hard JavaScript ·

Sliding window maximum

/**
 * @param {number[]} nums
 * @param {number} k
 * @returns {number[]}
 */
function window_max(nums, k)

window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)  // -> [3, 3, 5, 5, 6, 7]
window_max([1], 1)  // -> [1]

• #1Anthropic Claude Opus 5.5solved · 10 of 10 testsanswer in 6.4 s · runtime 679 ms · $0.01

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)expected [3, 3, 5, 5, 6, 7]	1 ms
  ✓	window_max([1], 1)expected [1]	1 ms

  ✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 401 ms⏱ 270 ms
  Code

  function window_max(nums, k) {
    const n = nums.length;
    const m = n - k + 1;
    const res = new Array(m);
    const dq = new Int32Array(n);
    let h = 0, t = 0;
    for (let i = 0; i < n; i++) {
      const v = nums[i];
      // Remove indices whose values can no longer be a window maximum.
      while (t > h && nums[dq[t - 1]] <= v) t--;
      dq[t++] = i;
      // Drop the front index once it leaves the window.
      if (dq[h] <= i - k) h++;
      if (i >= k - 1) res[i - k + 1] = nums[dq[h]];
    }
    return res;
  }

• #1DeepSeek V4.1 Flashsolved · 10 of 10 testsanswer in 755 ms · runtime 717 ms · $0.0001

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)expected [3, 3, 5, 5, 6, 7]	2 ms
  ✓	window_max([1], 1)expected [1]	1 ms

  ✓ 3 ms✓ 1 ms✓ 2 ms✓ 3 ms✓ 1 ms✓ 1 ms⏱ 396 ms⏱ 306 ms
  Code

  function window_max(nums, k) {
    const n = nums.length;
    const res = new Array(n - k + 1);
    const dq = new Int32Array(n); // indices, monotonic decreasing by value
    let head = 0, tail = 0, ri = 0;
    for (let i = 0; i < n; i++) {
      const v = nums[i];
      // pop smaller/equal from back
      while (tail > head && nums[dq[tail - 1]] <= v) tail--;
      dq[tail++] = i;
      // remove out-of-window from front
      if (dq[head] <= i - k) head++;
      if (i >= k - 1) res[ri++] = nums[dq[head]];
    }
    return res;
  }

• #1OpenAI GPT-6.1 Terrasolved · 10 of 10 testsanswer in 3.0 s · runtime 754 ms · $0.0011

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)expected [3, 3, 5, 5, 6, 7]	2 ms
  ✓	window_max([1], 1)expected [1]	1 ms

  ✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 3 ms✓ 3 ms⏱ 411 ms⏱ 332 ms
  Code

  function window_max(nums, k) {
    const n = nums.length;
    const result = new Array(n - k + 1);
    const deque = new Int32Array(n);
    let head = 0;
    let tail = 0;
  
    for (let i = 0; i < n; i++) {
      while (head < tail && deque[head] <= i - k) head++;
      while (head < tail && nums[deque[tail - 1]] <= nums[i]) tail--;
      deque[tail++] = i;
  
      if (i >= k - 1) result[i - k + 1] = nums[deque[head]];
    }
  
    return result;
  }

• #4Qwen3 Coder Nextnot solved · 9 of 10 testsanswer in 3.4 s · runtime 956 ms · $0.0002

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)expected [3, 3, 5, 5, 6, 7]	4 ms
  ✓	window_max([1], 1)expected [1]	4 ms

  ✓ <1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ <1 ms✓ 1 ms⏱ 440 ms⏱ time limit exceeded
  Code

  /**
   * @param {number[]} nums
   * @param {number} k
   * @returns {number[]}
   */
  function window_max(nums, k) {
      if (nums.length === 0 || k <= 0) return [];
      if (k > nums.length) k = nums.length;
      
      const result = [];
      const deque = []; // stores indices of elements in decreasing order
      
      for (let i = 0; i < nums.length; i++) {
          // Remove indices that are out of the current window
          while (deque.length > 0 && deque[0] <= i - k) {
              deque.shift();
          }
          
          // Remove indices whose corresponding values are less than current element
          // This maintains decreasing order in the deque
          while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
              deque.pop();
          }
          
          // Add current index to deque
          deque.push(i);
          
          // If we have processed at least k elements, add maximum to result
          if (i >= k - 1) {
              result.push(nums[deque[0]]);
          }
      }
      
      return result;
  }

  Second try

  not solved · 9 of 10 testsanswer in 3.0 s · $0.0003

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)expected [3, 3, 5, 5, 6, 7]	2 ms
  ✓	window_max([1], 1)expected [1]	3 ms

  ✓ <1 ms✓ 4 ms✓ 2 ms✓ 17 ms✓ 2 ms✓ <1 ms⏱ 468 ms⏱ time limit exceeded

  Code

  /**
   * @param {number[]} nums
   * @param {number} k
   * @returns {number[]}
   */
  function window_max(nums, k) {
      if (nums.length === 0 || k <= 0) return [];
      if (k > nums.length) k = nums.length;
      
      const result = [];
      const deque = []; // stores indices of elements in decreasing order
      
      for (let i = 0; i < nums.length; i++) {
          // Remove indices that are out of the current window
          while (deque.length > 0 && deque[0] <= i - k) {
              deque.shift();
          }
          
          // Remove indices whose corresponding values are less than current element
          while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
              deque.pop();
          }
          
          deque.push(i);
          
          if (i >= k - 1) {
              result.push(nums[deque[0]]);
          }
      }
      
      return result;
  }

Tokens cost: $0.01 · How rounds are run and scored →