0

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.

Community
  • 1
  • 1
Harsha Reaper
  • 129
  • 1
  • 10
  • Is your distance scalar or a direction? E. g. is the closest smallest element for 3 with distance 1 in [1, 0, 3, 1] the preceding 0 or the succeeding 1? What about distance -1? – le_m Jun 08 '16 at 16:48
  • Solve the linked question, and then just add k to the index of each query before answering the query. – j_random_hacker Jun 08 '16 at 17:18
  • @le_m distance's direction doesn't matter. It can be to the left or to the right. In your case you can pick either 0 or 1. – Harsha Reaper Jun 08 '16 at 17:51
  • 1
    @j_random_hacker I don't think that'd work. When you add k to the query you're finding the answer for a completely different element with a different value. – Harsha Reaper Jun 08 '16 at 17:54
  • @HarshaReaper *"The only difference is ..."* - obviously there are two differences, 1. the minimum distance k and 2. you want to find the closest smaller element in both direction, as opposed to the linked question where only forward traversal is performed. Correct? If yes, please update your question. – le_m Jun 08 '16 at 20:11
  • @le_m that's right. I forgot to mention that. Updated the question. – Harsha Reaper Jun 13 '16 at 14:32

1 Answers1

2

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]
Community
  • 1
  • 1
le_m
  • 19,302
  • 9
  • 64
  • 74