01_Sequences

Arrays and Strings.

https://www.techinterviewhandbook.org/algorithms/array/

Array Cheatsheet

Arrays

Arrays hold values of the same type at contiguous memory locations. In an array, we're usually concerned about two things - the position/index of an element and the element itself.

Advantages

Disadvantages

Common terms​

Things to look out for during interviews​

Corner Cases​

Time Complexity​

Operation Big-O Note
Access O(1)  
Search O(n)  
Search (sorted array) O(log(n))  
Insert O(n) Insertion would require shifting all the subsequent elements to the right by one and that takes O(n)
Insert (at the end) O(1) Special case of insertion where no other element needs to be shifted
Remove O(n) Removal would require shifting all the subsequent elements to the left by one and that takes O(n)
Remove (at the end) O(1) Special case of removal where no other element needs to be

Resource

Array in Data Structure: What is, Arrays Operations [Examples]

01_Arrays

01_Arrays

Brute Force

The brute force approach tries every possible combination to check for a solution, without leveraging any special properties or optimizations of the data (such as sorted order). Typically involves: 

Drawbacks:

BruteForce_TwoSum.gif

def brute_force_two_sum(nums, target):
    # Iterate through each element in the list
    for i in range(len(nums)):
        # For each element, check every other element that comes after it
        for j in range(i + 1, len(nums)):
            # Check if the current pair sums to the target
            if nums[i] + nums[j] == target:
                return (i, j)  # Return the indices as a tuple
    # If no pair is found that adds up to the target, return None
    return None

# Example usage:
nums = [2, 7, 11, 15]
target = 9

result = brute_force_two_sum(nums, target)
if result:
    print("Pair found at indices:", result)
else:
    print("No pair found that adds up to the target.")

01_Arrays

Two Pointers: Inward Traversal

A pointer is a variable that represents and index or position within a data structure, such as an Array or Linked List. With Two pointers we can make comparisons, with a pointer at two different positions, and infer a decision based on that. 

TwoPointer-InwardTraversal.gif

When to use:

Real-World Example:

def pair_sum_sorted(nums: List[int], target: int) -> List[int]:
  left, right = 0, len(nums)-1
  while left < right:
    sums = nums[left] + nums[right]
    # if the sum is smaller, increment the left pointer, aiming 
    # to increase the sum towards the target value
    if sums < target:
      left += 1
    # if the sum is larger, decrement the right pointer, aiming 
    # to decrease the sum towards the target value
    elif sums > target:
      right -=1
    # If target pair is found return its indices 
    else: 
      return [left,right]
  return []

01_Arrays

Two Pointers: Unidirectional Traversal

TwoPointer-UnidrectionalTraversal.gif

def shift_zeros_to_the_end(nums: List[int])-> None:
 # The 'left' pointer is used to position non-zero elements.
 left = 0
 # Iterate through the array using a 'right' pointer to locate non-zero
 # elements.
 for right in range(len(nums)):
   if nums[right] != 0:
     nums[left], nums[right] = nums[right], nums[left]
     # Increment 'left' since it now points to a position already occupied
     # by a non-zero element.
     left += 1

01_Arrays

Two Pointers: Stage Traversal

twopointer-stagetraversal-partitionbyparity.gif

Problem: Partition Array by Parity

Description:

Given an integer array nums, rearrange the array in-place such that all even numbers appear before all odd numbers. The order of the elements within the even or odd group does not matter.

Return the array after rearrangement.

You must solve the problem without using extra space (i.e. in O(1) extra space) and in one pass if possible.

Example 1:

Input: nums = [3, 8, 5, 12, 7, 4, 6] Output: [8, 12, 4, 6, 3, 5, 7] Explanation: The even numbers [8, 12, 4, 6] appear before the odd numbers [3, 5, 7]. Note that the order within each group does not matter.

Example 2:

Input: nums = [1, 3, 5, 7] Output: [1, 3, 5, 7] Explanation: Since there are no even numbers, the array remains unchanged.

Constraints:

  1. Initialization:
    The script starts with two pointers:

    • left at the beginning (index 0)
    • right at the end (last index)

  2. Stage Traversal:
    In each loop iteration:

    • It prints the current array and the positions (and values) of the two pointers.
    • If the number at the left pointer is even, that element is already in the correct half, so the left pointer is moved right.
    • If the number at the right pointer is odd, that element is in the correct half, so the right pointer is moved left.
    • If neither of those conditions holds (meaning the left number is odd and the right number is even), the two values are swapped. This moves the even number toward the left and the odd number toward the right.

  3. Termination:
    The loop ends when the left pointer is no longer less than the right pointer. At that point, the array is partitioned with evens on the left and odds on the right.

 

def partition_by_parity(nums):
    left = 0                      # Initialize the left pointer at the beginning.
    right = len(nums) - 1         # Initialize the right pointer at the end.
    print("Initial array:", nums)

    while left < right:
        print("\nCurrent array:", nums)
        print(f"Left pointer at index {left} with value {nums[left]}")
        print(f"Right pointer at index {right} with value {nums[right]}")

        # If the left element is even, it's already in the correct partition.
        if nums[left] % 2 == 0:
            print(f"{nums[left]} is even, so move the left pointer right.")
            left += 1
        # If the right element is odd, it's already in the correct partition.
        elif nums[right] % 2 == 1:
            print(f"{nums[right]} is odd, so move the right pointer left.")
            right -= 1
        # Otherwise, the left element is odd and the right element is even.
        # In that case, swap them.
        else:
            print(f"Swapping {nums[left]} (odd) and {nums[right]} (even).")
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    print("\nFinal partitioned array:", nums)

# Example usage:
nums = [3, 8, 5, 12, 7, 4, 6]
partition_by_parity(nums)

 

01_Arrays

Sliding Window: Fixed

A subset of the Two Pointer Method, but uses left and right pointers to define the bounds of a "window" in iterable data structures like arrays. The window defines the subcomponent, like subarray or substring, and it slides across the data structure in one direction, searching for a subcomponent that meets a certain requirement. 

When to use:

Brute Force:

Real-World Example:

Buffering in Video Streaming

01_Arrays

Sliding Window: Dynamic

01_Arrays

Traversing Array From The Right

right_traversal.gif

Find Last Occurrence of Target in Array

Description:
Given an integer array nums and an integer target, return the index of the last occurrence of target in nums. If the target is not found, return -1.

You must solve this problem with an efficient O(n) time solution by traversing the array from right to left.

Example 1:

Input: nums = [1, 3, 5, 3, 2], target = 3
Output: 3
Explanation: The target 3 appears at indices 1 and 3, but its last occurrence is at index 3.

Example 2:

Input: nums = [1, 2, 3, 4], target = 5
Output: -1
Explanation: The target 5 is not present in the array.

Constraints:

from typing import List

def find_last_occurrence(nums: List[int], target: int) -> int:
    """
    Returns the index of the last occurrence of target in nums.
    If the target is not found, returns -1.
    """
    # Traverse from rightmost index to left
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] == target:
            return i
    return -1

# Example usage:
nums = [1, 3, 5, 3, 2]
target = 3
result = find_last_occurrence(nums, target)
print("Last occurrence of", target, "is at index:", result)
01_Arrays

Sorting The Array

When you receive an unsorted array and decide to sort it before applying the two-pointer technique, the overall time complexity is dominated by the sorting step.

Thus, the overall time complexity becomes:
O(n log n) + O(n) = O(n log n)

 

If the array is already sorted, then you only pay the O(n) cost for the two-pointer traversal, without the additional O(n log n) sorting cost.

01_Arrays

Index as a Hash Key

String Cheatsheet

A string is a sequence of characters. Many tips that apply to Arrays also apply to Strings.

Time complexity​

A Strings is an array of characters, so the time complexities of basic string operations will closely resemble that of array operations.

Operation Big-O
Access O(1)
Search O(n)
Insert O(n)
Remove O(n)

Operations involving another String​

Here we assume the other string is of length m.

Operation Big-O
Find substring O(n.m)
Concatenating strings O(n + m)
Slice O(m)
Split (by token) O(n + m)
Strip (remove leading and trailing whitespaces) O(n)

Things to look out for during interviews​

Corner cases​

02_Strings

02_Strings

Counting Characters in a String

String of unique characters​

A neat trick to count the characters in a string of unique characters is to use a 26-bit bitmask to indicate which lower case latin characters are inside the string.

mask = 0
for c in word:
  mask |= (1 << (ord(c) - ord('a')))

To determine if two strings have common characters, perform & on the two bitmasks. If the result is non-zero, ie. mask_a & mask_b > 0, then the two strings have common characters.

02_Strings

String of Unique Characters

Counting characters​

Often you will need to count the frequency of characters in a string. The most common way of doing that is by using a hash table/map in your language of choice. 

If you need to keep a counter of characters, a common mistake is to say that the space complexity required for the counter is O(n). The space required for a counter of a string of latin characters is O(1) not O(n). This is because the upper bound is the range of characters, which is usually a fixed constant of 26. The input set is just lowercase Latin characters.

02_Strings

Anagram

An anagram is word switch or word play. It is the result of rearranging the letters of a word or phrase to produce a new word or phrase, while using all the original letters only once.

In interviews, usually we are only bothered with words without spaces in them.

To determine if two strings are anagrams, there are a few approaches:

02_Strings

Palindrome

Palindrome​

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as madam or racecar.

Here are ways to determine if a string is a palindrome:

The order of characters within the string matters, so hash tables are usually not helpful.

When a question is about counting the number of palindromes, a common trick is to have two pointers that move outward, away from the middle.