Leet code - Sliding window

sliding-window.md

Static size sliding window:

What can be achieved:

• We can iterate over all contiguous subsets of elements with a given size of a given sequence of elements with a good time complexity scalability.

// todo

Dynamic size sliding window:

What can be achieved:

• The sliding window can iterate over all contiguous elements (various sizes) of a given sequence of elements that that are limited by a certain constraint with a good time complexity scalability.

How to identify:

• The requested answer relates to a contiguous sequence of elements (e.g. Longest Substring with At Most Two Distinct Characters)
• It has a constraint (e.g. Longest Substring with At Most Two Distinct Characters).
• We can specify a valid window that satisfies the constraint.
• We can maintain the window state while expading it or shrinking it and know at all times if adding a new element breaks the constraint.

Implementing:

• Specify a window that will be valid for the entire iteration.
• Expand the size of the window if we can without making it invalid.
• Shrink the window if we can't expand the window.
• Everytime we try to expand the window we need to make sure that it will remain valid. For this we might need to keep track of the state of the window and check if the window will remain valid when the new element is added. The window state needs to be updated on every shrinkage and expansion.

Complexity: The complexity of the iteration is O(n) because each element is evaluated twice, once for each of the pointers which is O(2n) and can be simplified to O(n). The iteration will have a time complexity o O(2), because it will only need two pointers to do so.

Notes:

• The time and space complexity for the verification of the window validity and calculating the answer will depend on the data structures used in the specific problem.
• If we check all the conditions but we can't formulate a valid window we might want to think about a similar problem that can be solved with a sliding window that can be used to solve this one (e.g. Subarrays with K Different Integers can be broken down into two simultaneous executions of the Subarrays with at most K Different Integers).

Basic template:

function init(state: any) {
  // Initializes the state
}

function canExpand(state: any, element: any) {
  // Check the state to see if we can add the element to the window whilst maintaining it valid.
}

function addElement(state: any, element: any) {
  // Update the state of the window.
  // Update the answer if necessary.
}

function removeElement(state: any, element: any) {
  // Update the state of the window.
  // Update the answer if necessary.
}

function getAnswer(state) {
  // Return the pre calculated answer.
}

function windowLength(i: number, j: number): number {
  return j - i + 1
}

function iterate(array: Number[]): number {
    let n = array.length;
    let i = 0;
    let j = 0;
    let state = {};
    init(state);
    // Run until both indexes are out of bounds
    while(i < n && j < n) {
        if(canExpand(state, array[j])){
          // Expand the window
          addElement(state, array[j]);
          j++;
        } else {
          // Shrink the window
          removeElement(state, array[i]);
          i++;
        }
    }
    return getAnswer(state);
};

Example: Longest Substring with At Most Two Distinct Characters

Checklist:

• We have a substring, so we are dealing with a contiguous sequence of elements.
• We have a constraint, 'with at Most Two Distinct Characters'.
• We can use the constraint to define a valid window and maintain it:
  • Window: A substring with at most two distinct characters.
  • Validity: The window will be valid when empty because it will still be a substring with at most two distinct characters since it will have 0 characters. It will remain valid if we do not allow it to have more than two distinct characters.

Now that we know that this can be solved with the sliding window we just need to define the state and implement the methods of the template.