CODEWITHSUNDEEP
algorithm
Harsha Reaper
Harsha Reaper

Reputation: 129

Given an array of unique positive integers, find the closest smaller element for each element, but at a distance of atleast k

The question I'm referring to is similar to this one. The only differences are 1.) There should be a distance of atleast 'k' units from the current element to the closest smaller element that we pick. 2.) The element can be picked from either direction, towards the left or towards the right. So for example, if k=4 and there is a smaller element right next to the current one, we can't pick it as it's too close.

I tried implementing it the same way as the other solution. The change I made is, every time an element is removed from the stack, if it's actually smaller than the current element but got removed just because it's closer than k units, then I add the element back to the stack once I find the answer for the current element and then move on to the next element. This seems to work but I'm sure there is a more efficient way to solve this. Any suggestions would be very helpful.

Upvotes: 0

Views: 407

Answers (1)

le_m
le_m

Reputation: 20228

Solution with run-time and space complexity in O(n)

Forward traversal only: The following algorithm is a modification of the answer to Given an array, find out the next smaller element for each element and returns the nearest smaller successor for each element of the input array with a guaranteed minimum distance between the element and the successor:

// Traversal in forward direction only:
function smaller(array, distance) {
    var length = array.length,
        result = new Array(length).fill(null),
        stack = [];
    
    // Forward pass:
    for (var i = 0, j = distance; j < length; ++i, ++j) {
      while (stack.length > 0 && array[j] < array[stack[stack.length - 1]]) {
        result[stack.pop()] = array[j];
      }
      stack.push(i);
    }
    return result;
}

console.log(smaller([0, 2, 1], 0)); // [null, 1, null]
console.log(smaller([5, 2, 1, 7, 6, 0], 1)); // [1, 0, 0, 0, null, null]

Forward and backward traversal: The following algorithm returns the nearest smaller successor or predecessor for each element of the input array with a guaranteed minimum distance between the element and the successor or predecessor.

It works similar to the first algorithm, but traverses the array in both directions and stores the indices, not the values of the smaller elements. The nearest smaller elements are chosen from the results of both passes in a final third pass:

// Traversal in both directions:
function smaller(array, distance) {
    var length = array.length,
        forward = new Array(length).fill(null),
        backward = new Array(length).fill(null),
        stack = [];
  
    // Forward pass:
    for (var i = 0, j = distance; j < length; ++i, ++j) {
      while (stack.length > 0 && array[j] < array[stack[stack.length - 1]]) {
        forward[stack.pop()] = j;
      }
      stack.push(i);
    }

    // Backward pass:
    stack = [];
    for (var i = length - 1, j = length - distance - 1; j >= 0; --i, --j) {
      while (stack.length > 0 && array[j] < array[stack[stack.length - 1]]) {
        backward[stack.pop()] = j;
      }
      stack.push(i);
    }
    
    // Pick closest elements from both passes:
    for (var i = 0; i < length; ++i) {
      if (backward[i] !== null) {
        if (forward[i] !== null && forward[i] - i < i - backward[i]) {
          forward[i] = array[forward[i]];
        } else {
          forward[i] = array[backward[i]];
        }
      } else if (forward[i] !== null) {
        forward[i] = array[forward[i]];
      } 
    }
    return forward;
}

console.log(smaller([0, 2, 1], 0)); // [null, 0, 0]
console.log(smaller([5, 2, 1, 7, 6, 0], 1)); // [1, 0, 0, 2, 1, null]

Upvotes: 2

Related Questions