Educative Modules

[[1-SlidingWindow]] [[2-RotatedArray]]

Link

Given a large array of integers and a window size of w find the current maximum value in the window as the window slides through the entire array.

Let's try to find all maximums for w = 3:

[-4, 2, -5, 3, 6]

Step 1: for the first 3 elements, max is 2.

[-4, 2, -5], 3, 6
     * 

Step 2: Slide window one position to right and the max is now 3

-4, [2, -5, 3], 6
            * 

Step 3: In the last window the max is 6.

-4, 2, [-5, 3, 6]

let ffindMaxSlidingWindow = function(arr, windowSize) {
  let result = []

  if (arr.length == 0){
    return result;
  }

  if (windowSize > arr.length) {
    return result;
  }

  let window_ = 0;
  // find max for first window
  for (let i = 0; i < windowSize; i++) {
    while(window_.length > 0 && arr[i] >= arr[window_[window_.length - 1]]){
      window_.pop();
    }
    window.push(i);
  }

  result.push(arr[window_[0]])

  for (let i = windowSize; i < arr.length; i++){
    // remove all numbers that are smaller than the current max from the list
    while (window_.length > 0 && arr[i] >= arr[window_[window_.length -1]]) {
      window_.pop();
    }
    // remove first number if it doesn't fall in window
    if (window_.length > 0 && (window_[0] <= i - windowSize>)){
      window_.shift();
    }
    window_.push(i)
    result.push(arr[window_[0]])
  }
  return result;
}

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log("Array = " + array);
console.log("Max = " + ffindMaxSlidingWindow(array, 3));
// Max = 3,4,5,6,7,8,9,10

let array1 = [10, 6, 9, -3, 23, -1, 34, 56, 67, -1, -4, -8, -2, 9, 10, 34, 67]  
console.log("Array = " + array1);
console.log("Max = " + ffindMaxSlidingWindow(array1, 3))
// Max = 10,9,23,23,34,56,67,67,67,-1,-2,9,10,34,67

The runtime complexity in linear, O(n).

Every element is pushed and popped from the deque only once in a single traversal.

Memory complexity is linear, O*(w), where w is the window size

[[0-Index]]

Search for number in sorted array, with unique elements, that has been rotated by some arbitrary number. Return -1 if it doesn't exist

**Assume array does not contain duplicates

• Linear Search is not an acceptable solution
• Try to solve with binary search

Note: binary search requres a sorted array

const values = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

const search = (val, arr) => {
  for (let i = 0; i < arr.length; i++) {
   if(val === arr[i]) {
     return i;
   }
  }
  return -1;
}

1. Always dealing with lower and upper limits
2. Cut at middle, if not found, split sides at middle of each side until found

const binary = (val, arr) => {
  // create lower value
  let lower = 0;
  // create upper value
  let upper = arr.length - 1;

  // keep iterating as long as lower boundary is less than upper boundary
  while(lower <= upper) {
    // get middle index of array
    const middle = lower + Math.floor((upper - lower)/2)

    // if search val is middle # between lower and upper, return middle
    if (val === arr[middle]){
      return middle;
    }

    /* if search val is less than middle number:
        1. set upper to middle - 1
        2. set lower to middle + 1
    */
    if (val < arr[middle]){
      upper = middle - 1;
    } else {
      lower = middle + 1;
    }
  }
  return -1;
}

1. Sorted array

2. Cut in half

3. Proceed to left;
    search left

4. Proceed to right;
    search right

5. Repeat

Issue: Only one half of the array remains sorted if rotated

1. If number n is within sorted half, it is a basic binary search
2. Otherwise, discard sorted half and keep unsorted to be examine

-- Since we're partitioning each step, O(log n)

Solution 1: Recursive

let binarySearch = function(arr, start, end, key) {
  // assuming all the keys are unique.
  if (start > end) {
    return -1;
  }

  let mid = start + Math.floor((end - start) / 2);

  if (arr[mid] === key) {
    return mid;
  }

  if (arr[start] <= arr[mid] && key <= arr[mid] && key >= arr[start]) {
    return binarySearch(arr, start, mid - 1, key);
  }

  else if (arr[mid] <= arr[end] && key >= arr[mid] && key <= arr[end]) {
    return binarySearch(arr, mid + 1, end, key);
  }

  else if (arr[end] <= arr[mid]) {
    return binarySearch(arr, mid + 1, end, key);
  }

  else if (arr[start] >= arr[mid]) {
    return binarySearch(arr, start, mid - 1, key);
  }

  return -1;
};

let binarySearchRotated = function(arr, key) {
  return binarySearch(arr, 0, arr.length - 1, key);
};

let v1 = [6, 7, 1, 2, 3, 4, 5];
console.log("Key(3) found at: " + binarySearchRotated(v1, 3));
console.log("Key(6) found at: " + binarySearchRotated(v1, 6));

let v2 = [4, 5, 6, 1, 2, 3];
console.log("Key(3) found at: " + binarySearchRotated(v2, 3));
console.log("Key(6) found at: " + binarySearchRotated(v2, 6));

Solution 2: Iterative

The runtime complexity of this solution is logarithmic O(log n).

The memory complexity of this solution is constant, O(1).