algos using Sliding Window Techniques

algos-sliding-window-techniques.md

Sliding Window Problems (Types):

Fast / Slow

• Start with a 'fast' pointer and a 'slow' pointer
• Once you have a valid substring within the fast pointer then: you start shrinking the slow until you have a valid substring.

1. BitFlip
2. Min. Window Substring
3. Consecutive Subarray Sum

Fast / Catch-up

• Start with a 'fast' pointer and a 'slow' pointer
• Once you have a meet a valid condition at fast pointer then: the slow pointer "jumps" to the fast position.

1. Max Consecutive Sum.
2. Buy & Sell Stocks

Fast / Lag

• The slow pointer here is lagging behind, keeping track of the choices made. (Hueristics)

1. House Robber

Front / Back

• The two pointers are coming from oppositing directions across a linear path.

1. Rainwater
2. Sorted Two Sum

js-build-hashkey-map-set.js

(() => {
  // input: "testttf"
  // returns: 
  //  Map { t: 4, e: 1, s: 1, f: 1 }
  //  - key: t has 4 entries.
  //  - key: e has 1 entries.
  //  - key: s has 1 entries.
  //  - key: f has 1 entries.
  
  let input     = "testttf";
  let inputArr  = [...input];

  // must be written as declaration or expression with lexical scope context
  // can NOT be an arrow (annoymous) function
  // function(ele, ?index, ?array)
  const mapHelper = function(ele) {
    if (this.has(ele)) {
      this.set(ele, this.get(ele) + 1);
    } else {
      this.set(ele, 1);
    }
    return ele;
  }

  // get unique letters in string
  const uniqueKeys = new Set([...inputArr]);

  // map letters to default of 0 in KeyValue pair [ { 'a': 0, 'b': 0, ... } ]
  const mappedKeys = new Map([...uniqueKeys].map(el => [ el, 0 ]));

  // create the HashMap key-value association
  [...input].map(mapHelper, mappedKeys);

  return mappedKeys.entries() ?? new Map();
})();

js-flatten-reducer.js

(() => {
  let input = [[0, 1], [2, 3], [4]];
  // input: [[0, 1], [2, 3], [4]]
  // returns:
  // Array(5) [0, 1, 2, 3, 4]  
  // function(accumulator, currentValue, currentIndex, array){ .. }
  const flattenReducer = function reducerFlattenFunct(accumulator, currentValue) {
      return accumulator.concat(currentValue);
  };
  return input.reduce(flattenReducer, []);  
})();