25:["$","title",null,{"children":"Data Structures and Algorithms/Patterns (DSA) for the Technical Interview | Jon Sundin | Observable"}] 4b:T587,

Arrays and Strings

In the context of algorithms, arrays and strings are similar. Arrays are ordered groups of elements (primitives or user-defined types) and strings are ordered groups of characters. Arrays and strings are common data structures used as inputs for a problem, so it makes sense to understand them well.

Common Patterns with Arrays and Strings

Two Pointers

This is a common technique to solve problems dealing with arrays and strings.

First off, what is a pointer?

A value that references or "points" to another value.

So, in the "two pointer" technique, we use two variables to store two indices that hold the addresses of two values in the input array or string.

One implementation of the "two pointer" technique might be:

  Assign each pointer the edge indices of the array or string and then iteratively move the pointers towards each other.
  This is what it could look like as JavaScript code:
  
    let left = 0;
    let right = input.length - 1;

Reverse a String

Squares of a Sorted Array

4c:T1254,

Sliding Window

The sliding window technique uses two pointers to implement the technique. The technique fundementally works with a subsequence, which is a contiguous section (all elements must be adjacent to each other in the original sequence and their original order) of a sequence (an array or a string).

Here are examples of a subsequences from the array sequence: [1, 2, 3, 4]


          Subsequence of 1: [1], [2], [3], [4]
          Subsequence of 2: [1, 2], [2, 3], [3, 4]
          Subsequence of 3: [1, 2, 3], [2, 3, 4]
          Subsequence of 4: [1, 2, 3, 4]

In the context of an array, a subsequence is called a subarray. In the context of a string, a substring. Subarray and substring is a "window". In coding, we can describe a subarray or substring with two pointers describing the left and right boundary indices of the subsequence.

Which type of programming problems is the "sliding window" technique useful?

When a problem mentions criteria regarding a valid subarray or substring

Constraint metric: sum of the subarray
A numeric restriction on the constraint metric: <= 10

Explicit: the problem will ask for valid subarrays
- Most common: best valid subarray (e.g. find the longest valid subarray)
- Finding the number of valid subarrays

Sliding Window Algorithm

Two pointers (variables that hold the value of an address or index of another value) keep track of the edge indices of the window: left and right. Another variable will hold the current (curr) sum of the sliding window. Lastly, another variable will hold the answer, the maximum sum of the subarray that is less than the target (k).

An outer loop is used to loop through the input array or string, and an inner loop is used to remove the left pointer value(s) if after incrementing the right pointer, the answer becomes invalid. This inner loop iterates until the condition: (curr > k), where each iteration that the condition is true, the left pointer value is subtracted the curr sum of the subarray. After the inner loop, the answer variable is assigned a new value based on a condition. With the outer loop completing, the answer variable is returned from the function.

Sliding Window Implementation

      
        function fn(nums, k){
          let left = 0
          let curr = 0
          let answer = 0
          for (let right = 0; right < nums.length; right++){
              curr += nums[right]
              while (curr > k){
                curr -= nums[left]
                left++
              }
              answer = max(answer, right - left + 1)
          return answer
        }

Pseudocode

      
        function fn(arr):
          left = 0
          for (int right = 0; right < arr.length; right++):
            Do some logic to "add" element at arr[right] to window

            while WINDOW_IS_INVALID:
              Do some logic to "remove" element at arr[left] from window
              left++

          Do some logic to update the answer

Here are some example problems:

Find the longest subarray with a sum less than or equal to k
Find the longest substring that had at most one
```
"0"
```
Find the number of subarrays that have a product less than k

Maximum Average Subarray 1

Max Consecutive Ones III

4d:[] 47:{"id":"9f875c550cfd69c3","slug":"dsa","title":"Data Structures and Algorithms/Patterns (DSA) for the Technical Interview","thumbnail":"d5c22b6464318874ad936fc20ec1971f7e1266dda18871d9261639e05f4f11e6","access_level":"public","create_time":"$D2023-10-27T18:07:46.430Z","update_time":"$D2023-12-13T00:34:19.107Z","view_time":null,"first_public_time":"$D2023-10-27T18:07:46.430Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"7b7f7fa7ca429840","login":"jmsundin","name":"Jon Sundin","avatar_url":"https://avatars-next.observableusercontent.com/6043a22ac664cd4184076efee342bd03ae711cd4d3bf18aa8ef6563f07039894","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":199,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"008d4210803f5c62","login":"jmsundin","name":"Jon Sundin","avatar_url":"https://avatars-next.observableusercontent.com/6043a22ac664cd4184076efee342bd03ae711cd4d3bf18aa8ef6563f07039894","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"008d4210803f5c62","login":"jmsundin","name":"Jon Sundin","avatar_url":"https://avatars-next.observableusercontent.com/6043a22ac664cd4184076efee342bd03ae711cd4d3bf18aa8ef6563f07039894","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Data Structures and Algorithms/Patterns (DSA) for the Technical Interview","cells":[{"id":30,"value":"

Data Structures and Algorithms/Patterns (DSA) for the Technical Interview

DSA Overview

\n Algorithm Code Templates\n

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":0,"value":"$4b","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":141,"value":"$4c","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":145,"value":"

Arrays and Strings

Common Patterns with Arrays and Strings

Two Pointers

Reverse a String

Squares of a Sorted Array

Sliding Window

Sliding Window Algorithm

Sliding Window Implementation

Maximum Average Subarray 1

Max Consecutive Ones III

Data Structures and Algorithms/Patterns (DSA) for the Technical Interview

DSA Overview

Prefix Sum

Running Sum of 1d Array

Minimum Value to Get Positive Step by Step Sum

K Radius Subarray Averages

O(n) String Building

Subarrays/Substrings, Subsequences, and Subsets

Subarrays/Substrings

Subsequences

Subsets

Hashing

Linked Lists

Stacks and Queues

Trees and Graphs

Heaps

Greedy Algorithms

Binary Search

Backtracking

Dynamic Programming