Home/Coding Guide/Apple Interview Questions
⌂ Main Page
Coding Interview Preparation Guide

Apple Interview Questions

A worked set of Apple-style interview challenges with solutions and notes.

Challenges on this page

Apple Interview Questions

Python
from typing import List

Real onsite interview question (07/2024)

From my own interview

Python
"""
Lava Island
A man is dropped at a known position (x, y) on a rectangular island of known dimensions (m by n).
He takes steps one at a time in the four cardinal directions (up, down, left, right) with equal probability for each step.
Write a function that computes the probability that the man has not walked off the island after S steps.

*********LAVA********
* |   |   |   |   | *
L |   | o |   |   | L
A |   |   |   |   | A
V |   |   |   |   | V
A |   |   |   |   | A
* |   |   |   |   | *
********LAVA*********

SOLUTION:

Assumptions: x and y coordinates are zero-based; origin - top left. m - number of rows (x coordinate),
n - number of columns (y coordinate).

Simulate a random path by taking S random steps
One random step (you have to change the x,y coordinates accordingly):
        4 
        |
1 - location - 3
        |
        2
If a random path ends in the lava, the person dies. If not, the person lives.
Repeat the random path simulation a meaningful large number of times, for example 100,000 times, and compute
the ratio of number of random paths when the person lived and the total number of paths. That will be
the estimated probability that the man has not walked off the island.        
        
"""
import random

def take_one_step() -> None:
    '''Take a random step in one of the four directions'''
    return random.randint(1,4)

def still_alive(m:int, n:int, x:int, y:int) -> bool:
    '''Compute if the man has stepped off the island'''
    return False if (x<0 or y<0 or x>=m or y>=n) else True

def take_one_path(m:int, n:int, x:int, y:int, S:int) -> bool:
    '''Simulate one path. Return True if the man lived, False otherwise'''
    for i in range(S):
        step = take_one_step()
        if step == 1:
            y -= 1
        elif step == 2:
            x += 1
        elif step == 3:
            y += 1
        elif step == 4:
            x -= 1
        else:
            raise ValueError('Step must be a value from 1 to 4.')
                
        # the path goes off the island
        if not still_alive(m,n,x,y):
            return False
       
    # the path stays on the island all the time
    return True        

def survival_probability(m:int=20, n:int=13, x:int=17, y:int=3, S:int=51) -> float:
    '''Run multiple simulations (num_iter times) and compute the estimated probability'''
    num_iter, lived = 1000000, 0
    for j in range(num_iter):
        if take_one_path(m,n,x,y,S):
            lived += 1
    return lived / num_iter


proba = survival_probability()
print('Survival probability:', proba)

# Answer for suggested inputs is 0.23075939104176435 (~23%).
# Multiple simulations with 1,000,000 iterations always achieve an answer of ~23% for suggested inputs.
Output
Survival probability: 0.230514
Python
# Solution that was only discussed due to a lack of time:
# Let the values in the matrix be the probabilities of the man getting to that point - so the points
# around the current location would contain 0.25 (1/4), the points around these points would be 1/16,
# and so on. Interviewer - we really need a scipy function for this because it's hard to implement it by hand.
# My suggestion in the end: we can run so many simulations (let's say 1000 or 10,000) of different paths
# that the man can take, and see the percentage of them ending in the lava vs. those ending in the island.
Python
m, n = 5, 11
x, y = 3, 8
S = 25
survival_probability(m,n,x,y,S)
Output
0.108277

Two real phone interview questions (08/2025)

From my own interview

Python
# Question 1a. Find elements that occur only in one of the two lists, but not in both?
# example: 
# a = [1, 4, 5]
# b = [1, 2, 3, 4]
# output: [2,3,5]

def find_difference1(listA, listB):
    #edge cases
    if not isinstance(listA, list) and not isinstance(listB, list):
        raise ValueError('Message')
    if not listA and not listB:
        return []
    if not listA:
        return listB
    if not listB:
        return listA

    setA = set(listA)
    setB = set(listB)

    differenceA = setA - setB
    differenceB = setB - setA

    return list(differenceA.union(differenceB))


def find_difference2(listA, listB):
    return [x for x in listA if x not in listB] + [y for y in listB if y not in listA]


def find_difference3(listA, listB):
    return list((set(listA) | set(listB)) - (set(listA) & set(listB)))


a = [1, 4, 5]
b = [1, 2, 3, 4]
print(find_difference3(a, b))
Output
[2, 3, 5]
Python
# Question 1b. What if both lists are sorted?
'''
If both lists are sorted, you can exploit that to compute the symmetric difference more efficiently,
without converting to sets (which lose ordering). You can do it in O(n + m) time using a two-pointer technique
(like merge in merge-sort):
'''
def symmetric_diff_sorted(a, b):
    i, j = 0, 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            # skip elements that are in both
            i += 1
            j += 1
        elif a[i] < b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    # append leftovers
    result.extend(a[i:])
    result.extend(b[j:])
    return result

# Example
a = [1, 4, 5]
b = [1, 2, 3, 4]
print(symmetric_diff_sorted(a, b))  # [2, 3, 5]
Output
[2, 3, 5]
Python
"""
 Question 2.
 Implement the MinStack class: 
 MinStack() initializes the stack object.
 void push(int val) pushes the element val onto the stack.
 void pop() removes the element on the top of the stack.
 int top() gets the top element of the stack.
 int getMin() retrieves the minimum element in the stack.
 You must implement a solution with O(1) time complexity for each function.
"""

class MinStack:
    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, val):
        self.stack.append(val)
        if not self.minStack or val <= self.minStack[-1]:
            self.minStack.append(val)

    def pop(self):
        if self.stack:
            top_el = self.stack.pop()
            if top_el == self.minStack[-1]:
                self.minStack.pop()

    def top(self):
        return self.stack[-1] if self.stack else None

    def getMin(self):
        return self.minStack[-1] if self.minStack else None


min_stack = MinStack()
min_stack.push(5)
min_stack.push(2)
min_stack.pop()
min_el = min_stack.getMin()
print(min_el)
Output
5

GPT-4o Generated Matrix Challenges

Search a 2D Matrix I

Given an m x n matrix with the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. Write an efficient algorithm that searches for a target value in the matrix. If the target value exists, return its position (row, column); otherwise, return (-1, -1).

Python
def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return (-1, -1)

    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1

    while left <= right:
        mid = (left + right) // 2
        mid_value = matrix[mid // cols][mid % cols]
        if mid_value == target:
            return (mid // cols, mid % cols)
        elif mid_value < target:
            left = mid + 1
        else:
            right = mid - 1

    return (-1, -1)

# Example usage
matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
print(search_matrix(matrix, 3))  # Output: (0, 1)
Output
(0, 1)

Search a 2D Matrix II

Given an m x n matrix with the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. Write an algorithm that searches for a target value in the matrix. Return true if the target value exists, and false otherwise.

Python
def search_matrix_ii(matrix, target):
    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1

    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1

    return False

# Example usage
matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
print(search_matrix_ii(matrix, 5))  # Output: True

Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each of the rows and columns is sorted in ascending order, find the k-th smallest element in the matrix.

Python
import heapq

def kth_smallest(matrix, k):
    n = len(matrix)
    min_heap = [(matrix[i][0], i, 0) for i in range(min(k, n))]
    heapq.heapify(min_heap)

    for _ in range(k - 1):
        num, row, col = heapq.heappop(min_heap)
        if col + 1 < n:
            heapq.heappush(min_heap, (matrix[row][col + 1], row, col + 1))

    return heapq.heappop(min_heap)[0]

# Example usage
matrix = [
  [1, 5, 9],
  [10, 11, 13],
  [12, 13, 15]
]
print(kth_smallest(matrix, 8))  # Output: 13

Find Peak Element in a 2D Matrix

Given an m x n matrix, find a peak element in the matrix. A peak element is an element that is greater than or equal to its four possible neighbors (left, right, top, bottom). For the boundary elements, we need to consider only three neighbors.

Python
def find_peak_grid(mat):
    def find_peak_col_index(mid):
        max_row_index = 0
        for row in range(len(mat)):
            if mat[row][mid] > mat[max_row_index][mid]:
                max_row_index = row
        return max_row_index

    left, right = 0, len(mat[0]) - 1

    while left <= right:
        mid = (left + right) // 2
        max_row_index = find_peak_col_index(mid)

        if mid > 0 and mat[max_row_index][mid] < mat[max_row_index][mid - 1]:
            right = mid - 1
        elif mid < len(mat[0]) - 1 and mat[max_row_index][mid] < mat[max_row_index][mid + 1]:
            left = mid + 1
        else:
            return (max_row_index, mid)

# Example usage
mat = [
  [1, 4, 3, 1],
  [3, 2, 1, 4],
  [6, 5, 4, 7]
]
print(find_peak_grid(mat))  # Output: (2, 3)

Given a m x n board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Python
def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != word[i]:
            return False
        
        temp, board[r][c] = board[r][c], '#'
        found = (dfs(r + 1, c, i + 1) or
                 dfs(r - 1, c, i + 1) or
                 dfs(r, c + 1, i + 1) or
                 dfs(r, c - 1, i + 1))
        board[r][c] = temp
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True

    return False

# Example usage
board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
]
print(exist(board, "ABCCED"))  # Output: True

Given an m x n matrix, write a function to return the number of diagonals that contain a target value. Diagonals can go from top-left to bottom-right or top-right to bottom-left.

Python
def diagonal_search(matrix, target):
    def check_diagonal(r, c, dr, dc):
        while 0 <= r < len(matrix) and 0 <= c < len(matrix[0]):
            if matrix[r][c] == target:
                return True
            r += dr
            c += dc
        return False

    count = 0
    for r in range(len(matrix)):
        if check_diagonal(r, 0, 1, 1):
            count += 1
        if check_diagonal(r, len(matrix[0]) - 1, 1, -1):
            count += 1

    for c in range(1, len(matrix[0])):
        if check_diagonal(0, c, 1, 1):
            count += 1
        if check_diagonal(0, len(matrix[0]) - 1 - c, 1, -1):
            count += 1

    return count

# Example usage
matrix = [
  [1, 2, 3],
  [4, 1, 6],
  [7, 8, 1]
]
print(diagonal_search(matrix, 1))  # Output: 4

Matrix Spiral Order

Given an m x n matrix, return all elements of the matrix in spiral order

Python
def spiral_order(matrix):
    result = []
    while matrix:
        result += matrix.pop(0)
        if matrix and matrix[0]:
            for row in matrix:
                result.append(row.pop())
        if matrix:
            result += matrix.pop()[::-1]
        if matrix and matrix[0]:
            for row in matrix[::-1]:
                result.append(row.pop(0))
    return result

# Example usage
matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
print(spiral_order(matrix))  # Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Matrix Median

Given a m x n matrix in which each row is sorted, find the median of the matrix.

Python
def matrix_median(matrix):
    import bisect

    def count_less_equal(x):
        count = 0
        for row in matrix:
            count += bisect.bisect_right(row, x)
        return count

    low, high = matrix[0][0], matrix[-1][-1]
    while low < high:
        mid = (low + high) // 2
        if count_less_equal(mid) < (len(matrix) * len(matrix[0]) + 1) // 2:
            low = mid + 1
        else:
            high = mid
    return low

# Example usage
matrix = [
  [1, 3, 5],
  [2, 6, 9],
  [3, 6, 9]
]
print(matrix_median(matrix))  # Output: 5

Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. The board is partially filled where empty cells are filled with the character '.'. A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated according to the rules.

Python
def is_valid_sudoku(board):
    def is_valid_unit(unit):
        unit = [i for i in unit if i != '.']
        return len(unit) == len(set(unit))

    for row in board:
        if not is_valid_unit(row):
            return False

    for col in zip(*board):
        if not is_valid_unit(col):
            return False

    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            block = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
            if not is_valid_unit(block):
                return False

    return True

# Example usage
board = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
print(is_valid_sudoku(board))  # Output: True

Island Count

Given a 2D matrix grid of 1s (land) and 0s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Python
def num_islands(grid):
    if not grid:
        return 0

    def dfs(r, c):
        if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] == '0':
            return
        grid[r][c] = '0'
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

# Example usage
grid = [
  ["1", "1", "0", "0", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "1", "0", "0"],
  ["0", "0", "0", "1", "1"]
]
print(num_islands(grid))  # Output: 3

These Apple questions can be found in other companies' notebooks (but they are still provided in this full Apple notebook)

Arrays and Strings

1. Two Sum (Editor's choice: Frequently asked by Apple) (A)
3. Longest Substring Without Repeating Characters (F)
8. String to Integer (atoi) (A)
12. Integer to Roman (A)
13. Roman to Integer (F)
15. 3Sum (Editor's choice: Frequently asked by Apple) (F)
16. 3Sum Closest (A)
49. Group Anagrams (F)
76. Minimum Window Substring (F)
125. Valid Palindrome (F)
238. Product of Array Except Self (F)
268. Missing Number (A)
387. First Unique Character in a String (A)
560. Subarray Sum Equals K (F)
977. Squares of a Sorted Array (F)
20. Valid Parentheses (notebook for stacks and queues)
42. Trapping Rain Water (Editor's choice: frequently asked by Apple) (G)

Linked Lists

2. Add Two Numbers (Editor's choice: frequently asked by Apple) (F)
21. Merge Two Sorted Lists (Editor's choice: frequently asked by Apple) (F)
206. Reverse Linked List (A)

Trees and Graphs

133. Clone Graph (F)
200. Number of Islands (F)
236. Lowest Common Ancestor of a Binary Tree (F)
329. Longest Increasing Path in a Matrix (G)
543. Diameter of Binary Tree (F)

Recursion

17. Letter Combinations of a Phone Number (G)
22. Generate Parentheses (G)
46. Permutations (F)
78. Subsets (F)
79. Word Search (A)

Sorting and Searching

4. Median of Two Sorted Arrays (no official solution) (G)
33. Search in Rotated Sorted Array (F)
56. Merge Intervals (Editor's choice: frequently asked by Apple) (G)
242. Valid Anagram (strings notebook)
349. Intersection of Two Arrays (Editor's choice: frequently asked by Apple) (F)
350. Intersection of Two Arrays II (F)
973. K Closest Points to Origin (G)

Dynamic Programming

5. Longest Palindromic Substring (G)
10. Regular Expression Matching (F)
53. Maximum Subarray (Editor's choice: frequently asked by Apple) (G)
121. Best Time to Buy and Sell Stock (Editor's choice: frequently asked by Apple) (G)
139. Word Break (F)

Design

146. LRU Cache (Editor's choice: frequently asked by Apple) (G)
155. Min Stack (G)
380. Insert Delete GetRandom O(1) (G)

Other

7. Reverse Integer (G)
771. Jewels and Stones (G)

Arrays and Strings

Apple likes to ask simple, basic array questions. We highly recommend you practice Two Sum and its variance, 3Sum

1. Two Sum (Editor's choice: Frequently asked by Apple)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2: Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3: Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

2 <= nums.length <= 104 -109 <= nums[i] <= 109 -109 <= target <= 109 Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Hint #1
A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.

Hint #2
So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?

Hint #3
The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

Python
# time = space = O(n)
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i

15. 3Sum (Editor's choice: Frequently asked by Apple)

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:
Input: nums = []
Output: []

Example 3:
Input: nums = [0]
Output: []

Constraints: * 0 <= nums.length <= 3000 * -105 <= nums[i] <= 105

Complexity * Brute force - three nested loops. Time c. O(n^3) * Optimal time c. - sorting = O(nlogn); nested loop = O(n^2)/2 => O(n^2). Therefore, O(nlogn + n^2) => O(n^2) * Space c. - no duplicates and i != j != k => total number of possible triplets is n/3. O(n/3) => O(n)

Python
def threeSum(nums: List[int]) -> List[List[int]]:
    '''
        My accepted solution
        Your runtime beats 93.44% of python3 submissions
        Your memory usage beats 98.69 % of python3 submissions
    '''
    
    n = len(nums)
    nums.sort()        
    res = set()                                               # helps avoid duplicates and decrease scpace complexity

    for i in range( n-1 ):

        if nums[i] > 0 or (i > 0 and nums[i] == nums[i-1]):   # next vals cannot sum to 0 in sorted arr if num[i] > 0
            continue                                          # it's a duplicate if nums[i] == nums[i-1]
                                                              # helps greatly decrease run time (per LeetCode metrics)
        l = i+1
        r = n-1

        while l < r:
            sum_ = nums[i] + nums[l] + nums[r]
            if sum_ < 0:
                l += 1
            elif sum_ > 0:
                r -= 1
            else:             
                res.add( (nums[i], nums[l], nums[r]) )
                l += 1
                r -= 1

    return list(res)


a1 = [-1, 0, 1, 2, -1, -4]
a2 = []
a3 = [0]

for a in [a1, a2, a3]:
    print( threeSum(a) )
Output
[(-1, -1, 2), (-1, 0, 1)]
[]
[]

42. Trapping Rain Water (Editor's choice: frequently asked by Apple)

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

image.png

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2: Input: height = [4,2,0,3,2,5] Output: 9

Constraints:

n == height.length 1 <= n <= 2 * 10^4 0 <= height[i] <= 10^5

Algorithm

Use stack to store the indices of the bars. Iterate the array: While stack is not empty and \text{height[current]}>\text{height[st.top()]}height[current]>height[st.top()] It means that the stack element can be popped. Pop the top element as \text{top}top. Find the distance between the current element and the element at top of stack, which is to be filled. \text{distance} = \text{current} - \text{st.top}() - 1distance=current−st.top()−1 Find the bounded height \text{bounded_height} = \min(\text{height[current]}, \text{height[st.top()]}) - \text{height[top]}bounded_height=min(height[current],height[st.top()])−height[top] Add resulting trapped water to answer \text{ans} \mathrel{+}= \text{distance} \times \text{bounded_height}ans+=distance×bounded_height Push current index to top of the stack Move \text{current}current to the next position

Python
# C++, time = space = O(n) 
int trap(vector<int>& height)
{
    int ans = 0, current = 0;
    stack<int> st;
    while (current < height.size()) {
        while (!st.empty() && height[current] > height[st.top()]) {
            int top = st.top();
            st.pop();
            if (st.empty())
                break;
            int distance = current - st.top() - 1;
            int bounded_height = min(height[current], height[st.top()]) - height[top];
            ans += distance * bounded_height;
        }
        st.push(current++);
    }
    return ans;
}

16. 3Sum Closest

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1: Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2: Input: nums = [0,0,0], target = 1 Output: 0 Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints:

3 <= nums.length <= 500 -1000 <= nums[i] <= 1000 -104 <= target <= 104

Python
# time = O(n^2), space = from O(logn) to O(n), depending on implementation of sorting algorithm
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        diff = float('inf')
        nums.sort()
        for i in range(len(nums)):
            lo, hi = i + 1, len(nums) - 1
            while (lo < hi):
                sum = nums[i] + nums[lo] + nums[hi]
                if abs(target - sum) < abs(diff):
                    diff = target - sum
                if sum < target:
                    lo += 1
                else:
                    hi -= 1
            if diff == 0:
                break
        return target - diff
Python
nums = [-1,2,1,-4]
target = 1
threeSumClosest(nums, target)

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:
Input: s = ""
Output: 0

Constraints: * 0 <= s.length <= 5 * 104 * s consists of English letters, digits, symbols and spaces

Python
# best solution
def lengthOfLongestSubstring(s: str) -> int:
    '''LeetCode solution beautified by me
       We use HashSet to store the characters in current window [i,j) (j = i initially).
       Then we slide the index j to the right. If it is not in the HashSet, we slide j further.
       Doing so until s[j] is already in the HashSet. At this point, we found the maximum size
       of substrings without duplicate characters start with index i.
       If we do this for all i, we get our answer
    '''
    mapp = {c:0 for c in s}
    left = 0
    max_len = 0
    for right, c in enumerate(s):
        mapp[c] += 1
        while mapp[c] > 1:
            mapp[ s[left] ] -= 1
            left += 1
        max_len = max(max_len, right - left + 1)

    return max_len

    
s1 = 'abcbacbb'
s2 = 'bbbbb'
s3 = 'pwwkew'
s4 = ''

# 3,1,3,0
for s in [s1, s2, s3, s4]:
    print( lengthOfLongestSubstring(s), end=', ' )
Output
3, 1, 3, 0,
Python
from collections import defaultdict
def lengthOfLongestSubstring2(s: str) -> int:
    ''' My Solution (Accepted)
        Iterate over each char in string with some logic    
    '''    
        
    curr, max_ = '', ''
    for idx, c in enumerate(s):
        if not curr:                             # add current char if curr is empty
            curr = c                        
        elif curr and c not in curr:             # add current char if it's not in curr
            curr += c
        elif curr and curr[-1] == c:             # reset curr if current char is also the last one in curr
            curr = c
        else:                                    # current char in curr, but not the last one - find its index in s,
            temp_idx = idx - 1                   # but not in curr(!) because curr may be shorter. Make curr include 
            while s[temp_idx] != c:              # everyting after (because there is no c) + c at current idx
                temp_idx -= 1
            curr = s[temp_idx+1 : idx+1]

        max_ = max(curr, max_, key=len)
                
    return len(max_)


def lengthOfLongestSubstring3(s: str) -> int:
    '''
        Another my solution
        Time c.  = O(3n) = O(n)
        Space c. = O(2n) = O(n)?
    '''
    def all_unique(s2: str) -> bool:
        stack = []
        for c in s2:
            if c not in stack:
                stack.append(c)
        return len(s2) == len(stack)
    
    i,j = 0,1
    max_len = 0
    length = len(s)
    while i < length and j < length:
        curr_str = s[i:j]
        if all_unique(curr_str):
            curr_len = len(curr_str)
            if curr_len > max_len:
                max_len = curr_len
            j += 1
        else:
            while i < j and not all_unique(s[i:j]):
                i += 1
    return max_len
        
    
    
def lengthOfLongestSubstring4(s: str) -> int:
    '''
        Brute force
        Time c.  = O((n^2)/2) = O(n^2)
        Space c. = O(n) because of curr_str? Or O(1)?
    '''
    max_len = 0
    for i in range(len(s)):
        for j in range(i+1, len(s)):
            curr_str = s[i:j]
            if len(curr_str) == len(set(curr_str)):
                curr_len = len(curr_str)
                if curr_len > max_len:
                    max_len = curr_len
    return max_len


s1 = 'abcbacbb'
s2 = 'bbbbb'
s3 = 'pwwkew'
s4 = ''

# 3,1,3,0
for s in [s1, s2, s3, s4]:
    print( lengthOfLongestSubstring(s), end=', ' )
    
print()    
for s in [s1, s2, s3, s4]:
    print( lengthOfLongestSubstring2(s), end=', ' )
Output
3, 1, 3, 0, 
3, 1, 3, 0,

49. Group Anagrams

Array of strs => group anagrams together (in any order). Anagram = word, phrase w/rearranged letters (typically original letters are used exactly once)

Example 1: Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2: Input: strs = [""] Output: [[""]]

Example 3: Input: strs = ["a"] Output: [["a"]]

Constraints: * 1 <= strs.length <= 104 * 0 <= strs[i].length <= 100 * strs[i] consists of lowercase English letters.

Python
from collections import defaultdict

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    '''
        My accepted solution
        Your runtime beats 45% of python3 submissions
        Your memory usage beats 55% of python3 submissions
        
        Time c.: O(NKlogK), where N = len(strs), K = max_len of s in strs.
        Outer loop = O(N) (iterate over strs), then sort each s in O(KlogK) time
        
        Space c.: O(NK) - content of res
    '''        
    res = defaultdict(list)
    for s in strs:
        res[ ''.join(sorted(s)) ].append(s)

    return res.values()


def groupAnagrams2(strs: List[str]) -> List[List[str]]:
    '''
        Optimized O(NK) time and space c. solution from LeetCode.
        Two str = anagrams iff their char counts are the same ==> transform each str into char count
        consisting of a tuple of 26 non-negative integers, one per letter, which are used as keys in hash map
    '''    
    res = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ ord(c)-ord('a') ] += 1
        res[ tuple(count) ].append(s)

    return res.values()

strs = ["eat","tea","tan","ate","nat","bat"]
groupAnagrams2(strs)
Output
dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])

76. Minimum Window Substring

Two strings s, t w/len m, n. Return minimum contiguous substring of s that includes each char in t (including duplicates). Return '' if none

Answer in testcases is unique.

Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2: Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints: * m == s.length * n == t.length * 1 <= m, n <= 105 * s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Sliding Window Algorithm * Two pointers, left and righ initially pointing to first elem in S. * Expand window with right pointer until we get a desirable window (contains all chars from T, but may not be the shortest). * Contract window with left pointer while is still desirable. * If window is not desirable any more, start with step 2 again

Python
def minWindow(s: str, t: str) -> str:
    '''
    My solution from scratch
    Time c. O(3n) => O(n)?
    Space c. O(n) because of res? 
    '''
    def build_map(string: str) -> str:        
        mapp = {}
        for c in string:
            if c in mapp:
                mapp[c] += 1
            else:
                mapp[c] = 1
        return mapp
    
    def is_map2_in_map1(map1: dict, map2: dict) -> bool:
        for k in map2:
            if k not in map1:
                return False
            if map1[k] < map2[k]:
                return False
        return True
    
    min_len = 10**5
    res     = ''
    map_t = build_map(t)
    l, r = 0, 1
    while l < r and r < len(s)+1:
        if is_map2_in_map1(build_map(s[l:r]), map_t):
            if len(s[l:r]) < min_len:
                min_len = len(s[l:r])
                res = s[l:r]
            l += 1
        else:
            r += 1
    return res
Python
def minWindow(s: str, t: str) -> str:
    '''
    My solution from scratch 2
    Time c. O(n)?
    Space c. O(n) because of res? 
    '''
    if len(t) > len(s):
        return ''
    elif t == s:
        return t
    res = ''
    min_len = float('inf')    
    d_t = dict()
    for c in t:
        d_t[c] = d_t.get(c, 0) + 1
    print(d_t)
    
    l,r = 0,1
    while l <=r and r < len(s):
        curr_str = s[l:r+1]        
        d_s = dict()
        for c in curr_str:
            d_s[c] = d_s.get(c, 0) + 1                        
        print('\tCurrent str:', curr_str)
        print('\tD_T:', d_t)
        print('\tD_S:', d_s)
                
        passed = True
        for k in d_t:
            if (k not in d_s) or (d_s[k] < d_t[k]):
                passed = False
                break
        print('\tPassed:', passed)
                
        if passed:
            if len(curr_str) < min_len:
                min_len = len(curr_str)
                res     = curr_str
            d_s[s[l]] -= 1
            l += 1
            print('\tNew l:', l)
        else:            
            r += 1            
            print('\tNew r:', r)
        print('Result:', res, '\n')     
    return res
Python
# my concise solution(based on Leetcode solution). Time/space c. O(n+m)
from collections import Counter

def minWindow(s, t):

    if not t or not s:
        return ''
    dict_t = Counter(t)                     # dict unique chars in t
    len_t  = len(dict_t)                    # count unique chars in t
    dict_curr = {}                          # dict unique chars in curr win
    len_curr  = 0                           # count unique chars in curr window
    l,r = 0,0
    res = float('inf'), None, None          # shortest window length, l, r

    while r < len(s):

        char = s[r]
        dict_curr[ char ] = dict_curr.get(char, 0) + 1
        if char in dict_t and dict_curr[char] == dict_t[char]:
            len_curr += 1

        while l <= r and len_curr == len_t:
            char = s[l]
            if r - l + 1 < res[0]:
                res = (r - l + 1, l, r)

            dict_curr[ char ] -= 1
            if char in dict_t and dict_curr[char] < dict_t[char]:
                len_curr -= 1
            l += 1

        r += 1
    return '' if res[0]==float('inf') else s[ res[1]:res[2]+1 ]
Python
# Leetcode solution
from collections import Counter


def minWindow2(s: str, t: str) -> str:
    '''
        LeetCode's solution. Time c. O(m+n)    
    '''    

    if not t or not s:
        return ''
        
    l, r     = 0, 0
    dict_t   = Counter(t)                                     # count of all chars in t    
    required = len(dict_t)                                  # num of unique chars in t that must be in desired window
    
    formed = 0                                       # num unique chars from t in current window in desired frequency
                                                             # e.g. if t=="AABC" => two A's, one B, one C => formed=3
    
    window_counts = {}                                         # count of all unique chars in current window    
    ans = float("inf"), None, None                             # ans = tuple(window length, left, right)

    while r < len(s):

        
        char = s[r]                                                 # add one char from right
        window_counts[ char ] = window_counts.get(char, 0) + 1
        
        if char in dict_t and window_counts[ char ] == dict_t[ char ]:
            formed += 1                               # if current char's frequency == desired count, increment formed
        
        while l <= r and formed == required:                 # contract current window till until it's not 'desirable'
            char = s[l]
            
            if r - l + 1 < ans[0]:                                   # smallest window until now
                ans = (r - l + 1, l, r)

            
            window_counts[char] -= 1                                # char at `left` no longer part of current window
            if char in dict_t and window_counts[ char ] < dict_t[ char ]:
                formed -= 1
            
            l += 1                                                      # contract current window to look for new one
        
        r += 1                                                             # keep expanding once contracting is done
        
    return s[ ans[1]:ans[2]+1 ] if not ans[0]==float("inf") else ''


s = "ADOBECODEBANC"
t = "ABC"
minWindow(s, t)
Output
'BANC'

A small improvement to the above approach can reduce the time complexity of the algorithm to O(2∗∣filtered_S∣+∣T∣), where filtered_S is the string formed from S by removing all the elements not present in T. This complexity reduction is evident when |filtered_S| <<< |S|∣filtered_S∣<<<∣S∣

Python
# Leetcode solution 2
def minWindow3(s: str, t: str) -> str:
    """
    Optimized Leetcode solution
    """
    
    if not t or not s:
        return ""

    dict_t = Counter(t)
    required = len(dict_t)

    # Leave only chars from s that occur in t
    filtered_s = []
    for i, char in enumerate(s):
        if char in dict_t:
            filtered_s.append((i, char))

    l, r = 0, 0
    formed = 0
    window_counts = {}

    ans = float("inf"), None, None

    # Same sliding window approach, but on as small list
    while r < len(filtered_s):
        character = filtered_s[r][1]
        window_counts[character] = window_counts.get(character, 0) + 1

        if window_counts[character] == dict_t[character]:
            formed += 1

        while l <= r and formed == required:
            character = filtered_s[l][1]

            end = filtered_s[r][0]
            start = filtered_s[l][0]
            if end - start + 1 < ans[0]:
                ans = (end - start + 1, start, end)

            window_counts[character] -= 1
            if window_counts[character] < dict_t[character]:
                formed -= 1
            l += 1    

        r += 1    
    return s[ ans[1]:ans[2]+1 ] if not ans[0]==float("inf") else ''
Python
samples = [ ("ADOBECODEBANC", "ABC"), ("a", "a"), ("a", "aa") ]
for sample in samples:
    print(minWindow(sample[0], sample[1]))
#Output: "BANC"
#Output: "a"
#Output: ""
Output
BANC
a

125. Valid Palindrome

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example 1: Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome

Example 2: Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.

Constraints: * 1 <= s.length <= 2 * 105 * s consists only of printable ASCII characters

Python
import string

def isPalindrome(s: str) -> bool:
    '''
        My accepted solution    
    '''    
    if not s:
        return False
    elif len(s) == 1:
        return True
    
    s = ''.join([c for c in s.lower() if c.isalnum()])
    l, r = 0, len(s) - 1
    while l < r:
        if not s[l] == s[r]:
            return False
        l += 1
        r -= 1
        
    return True


def isPalindrome2(s: str) -> bool:
    '''
       Leetcode solution (same approach)
    '''

    i, j = 0, len(s) - 1

    while i < j:
        while i < j and not s[i].isalnum():
            i += 1
        while i < j and not s[j].isalnum():
            j -= 1

        if s[i].lower() != s[j].lower():
            return False

        i += 1
        j -= 1

    return True

s1 = 'A man, a plan, a canal: Panama'
s2 = 'race a car'



isPalindrome(s1)
Output
True

238. Product of Array Except Self

Given int array nums, return array answer where answer[i] = product of all elems of nums except nums[i]. Product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer (but not of entire nums?). Algo must run in O(n) time, without the division operation.

Example 1: Input: nums = [1,2,3,4] Output: [24,12,8,6]

Example 2: Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

Constraints: * 2 <= nums.length <= 105 * -30 <= nums[i] <= 30 * The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer => cannot do product of all nums/nums[i]

Follow up: O(1) extra space complexity if not counting answer array?

Python
def productExceptSelf3(nums: list[int]) -> list[int]:
    '''
        My solution; works locally, exceeds time limit when submitted    
    '''
    
    answer = []
    for i in range( len(nums) ):
        product = 1
        for j in range( len(nums) ):
            if j != i:
                product *= nums[j]
        answer.append(product)

    return answer


def productExceptSelf2(nums: list[int]) -> list[int]:
    '''
        Leetcode solution 1. Time c. O(n), space c. O(n) because of two extra arrays   
    '''    
    length = len(nums)    
    L, R, answer = [0]*length, [0]*length, [0]*length
    
    L[0] = 1                                # L[i] - product of all elems to left. L[0] = 1 since nothing to left
    for i in range(1, length):        
        L[i] = nums[i-1] * L[i-1]

    R[-1] = 1                               # R[i] - product of all elems to right. R[-1] = 1 since nothing to right
    for i in reversed(range(length - 1)):        
        R[i] = nums[i + 1] * R[i + 1]
    print(L, R)

    for i in range(length):
        answer[i] = L[i] * R[i]

    return answer


def productExceptSelf(nums: list[int]) -> list[int]:
    '''
        Leetcode solution 2. Time c. O(n), space c. O(1). answer array = array L from solution 1
        and var R contains a running product of elems to right, replacing array R from solution 1
    '''
    length = len(nums)
    answer = [0]*length

    answer[0] = 1                     # answer[i] - product of all elems to left. answer[0] = 1 since nothing to left
    for i in range(1, length):
        answer[i] = nums[i - 1] * answer[i - 1]

    
    R = 1                             # R - running product of elems to right. First R = 1 since nothing to right
    for i in reversed(range(length)):
        answer[i] = answer[i] * R
        R *= nums[i]

    return answer


    
nums = [1,2,3,4]
print( productExceptSelf2(nums) )

nums = [-1,1,0,-3,3] 
print( productExceptSelf2(nums) )

nums = [1, 5, 7, 2] 
print( productExceptSelf2(nums) )
Output
[1, 1, 2, 6] [24, 12, 4, 1]
[24, 12, 8, 6]
[1, -1, -1, 0, 0] [0, 0, -9, 3, 1]
[0, 0, 9, 0, 0]
[1, 1, 5, 35] [70, 14, 2, 1]
[70, 14, 10, 35]

268. Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1: Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2: Input: nums = [0,1] Output: 2 Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3: Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8 Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

n == nums.length 1 <= n <= 104 0 <= nums[i] <= n All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Python
# time = space = O(n)
class Solution:
    def missingNumber(self, nums):
        num_set = set(nums)
        n = len(nums) + 1
        for number in range(n):
            if number not in num_set:
                return number
Python
# time = O(n), space = O(1)
class Solution:
    def missingNumber(self, nums):
        missing = len(nums)
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing
Python
# Gauss' Formula
# time = O(n), space = O(1)
class Solution:
    def missingNumber(self, nums):
        expected_sum = len(nums)*(len(nums)+1)//2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

387. First Unique Character in a String

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1: Input: s = "leetcode" Output: 0

Example 2: Input: s = "loveleetcode" Output: 2

Example 3: Input: s = "aabb" Output: -1

Constraints:

1 <= s.length <= 105 s consists of only lowercase English letters

Python
# time = O(n), space = O(1)
class Solution:
    def firstUniqChar(self, s: str) -> int:
        """
        :type s: str
        :rtype: int
        """
        # build hash map : character and how often it appears
        count = dict()
        for idx, ch in enumerate(s):
            if ch in count:
                count[ch] += 1
            else:
                count[ch] = 1
        
        # find the index
        for idx, ch in enumerate(s):
            if count[ch] == 1:
                return idx     
        return -1

560. Subarray Sum Equals K

Array of int nums and int k - return total num continuous subarrays with sum k

Example 1: Input: nums = [1,1,1], k = 2 Output: 2

Example 2: Input: nums = [1,2,3], k = 3 Output: 2

Constraints: * 1 <= nums.length <= 2 * 10^4 * -1000 <= nums[i] <= 1000 * -10^7 <= k <= 10^7

Idea: if curr_sum up to two indices, say i and j is at a difference of k i.e. sum[i]-sum[j] = k, the sum of elements lying between indices i and j is k, too

Python
from collections import defaultdict

def subarraySum(nums: List[int], k: int) -> int:
    '''
        Combined Leetcode and my solution. Time c. = space c. = n
        Lines that are commented out - case when you keep actual subarrays, not just their count
    '''    
    curr_sum   = 0
    hash_map    = defaultdict()
    hash_map[0] = 1
    count      = 0
        
    for i in range(len(nums)):
        
        curr_sum += nums[i]
        if curr_sum - k in hash_map:
            count += hash_map.get(curr_sum - k)
            
            #alist = hash_map[curr_sum - k]
            #for value in alist:
            #    res.append(nums[value+1: i+1])
                        
        hash_map[curr_sum] = hash_map.get(curr_sum, 0) + 1
        #hash_map[curr_sum].append(i)
        
    return count


nums = [1,1,1]
k = 2
print( subarraySum(nums, k) )

nums = [1,2,3]
k = 3
print( subarraySum(nums, k) )
Output
2
2

977. Squares of a Sorted Array (FB interview per LeetCode's Discussions)

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints: * 1 <= nums.length <= 104 * -104 <= nums[i] <= 104 * nums is sorted in non-decreasing order.

Follow up: Squaring, then sorting is very trivial. O(n) solution?

Intuition

Array A is sorted => negative elems with squares in decreasing order and non-negative elements with squares in increasing order.

For example, with [-3, -2, -1, 4, 5, 6], we have the negative part [-3, -2, -1] with squares [9, 4, 1], and the positive part [4, 5, 6] with squares [16, 25, 36]. Our strategy is to iterate over the negative part in reverse, and the positive part in the forward direction.

Algorithm

We can use two pointers to read the positive and negative parts of the array - one pointer j in the positive direction, and another i in the negative direction.

Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique

Python
def sortedSquares(nums: List[int]) -> List[int]:
    '''
        LeetCode solution    
    '''    
    n = len(nums)
    result = [0] * n
    left = 0
    right = n - 1
    for i in range(n - 1, -1, -1):
        if abs(nums[left]) < abs(nums[right]):
            square = nums[right]
            right -= 1
        else:
            square = nums[left]
            left += 1
        result[i] = square * square
                
    return result
Python
numss = [[-4,-1,0,3,10], [-7,-3,2,3,11], [-3, -1, 1, 3, 4, 5]]
for nums in numss:
    print(sortedSquares(nums))
# [0,1,9,16,100]
# [4,9,9,49,121]
# [1, 1, 9, 9, 16, 25]

20. Balanced parenthesis check (stack)

A very common interview question * scan string left to right, push every opening parenthesis to stack (last opening parenthesis to be closed first - FILO) * when encounter closing parenthesis, pop last opening p. from stack and see if a match * if yes, proceed, if no False; if stack runs out, and there are still closing p. - False * once all matched - check if stack is empty - True

Python
def balance_check(s):
    
    if len(s)%2 != 0:                                        # even number of brackets
        return False    
   
    opening = set('([{')                                     # opening brackets    
    
    matches = set([ ('(',')'), ('[',']'), ('{','}') ])       # matching Pairs
    
    stack = []                                               # list as a "Stack"
    
    for paren in s:                                          # check every parenthesis        
        
        if paren in opening:
            stack.append(paren)
        
        else:

            if len(stack) == 0:                              # Are there parentheses in Stack
                return False
            
            
            last_open = stack.pop()                          # check last open parenthesis

            if (last_open,paren) not in matches:
                return False
            
    return len(stack) == 0
Python
to_check = ['[]', '[](){([[[]]])}', '()(){]}']
for i in to_check:
    print(balance_check(i))

8. String to Integer (atoi)

(See also Facebook notebook for another solution)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function). The algorithm for myAtoi(string s) is as follows:

Read in and ignore any leading whitespace. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2). If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1. Return the integer as the final result.

Note: Only the space character ' ' is considered a whitespace character. Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1: Input: s = "42" Output: 42 Explanation: The underlined characters are what is read in, the caret is the current reader position. Step 1: "42" (no characters read because there is no leading whitespace) ^ Step 2: "42" (no characters read because there is neither a '-' nor '+') ^ Step 3: "42" ("42" is read in) ^ The parsed integer is 42. Since 42 is in the range [-231, 231 - 1], the final result is 42.

Example 2: Input: s = " -42" Output: -42 Explanation: Step 1: " -42" (leading whitespace is read and ignored) ^ Step 2: " -42" ('-' is read, so the result should be negative) ^ Step 3: " -42" ("42" is read in) ^ The parsed integer is -42. Since -42 is in the range [-231, 231 - 1], the final result is -42.

Example 3: Input: s = "4193 with words" Output: 4193 Explanation: Step 1: "4193 with words" (no characters read because there is no leading whitespace) ^ Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+') ^ Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit) ^ The parsed integer is 4193. Since 4193 is in the range [-231, 231 - 1], the final result is 4193.

Constraints:

0 <= s.length <= 200 s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

Python
# time = O(n), space = O(1)
class Solution:
    def myAtoi(self, input: str) -> int:
        sign = 1 
        result = 0
        index = 0
        n = len(input)
        
        INT_MAX = pow(2,31) - 1 
        INT_MIN = -pow(2,31)
        
        # Discard all spaces from the beginning of the input string.
        while index < n and input[index] == ' ':
            index += 1
        
        # sign = +1, if it's positive number, otherwise sign = -1. 
        if index < n and input[index] == '+':
            sign = 1
            index += 1
        elif index < n and input[index] == '-':
            sign = -1
            index += 1
        
        # Traverse next digits of input and stop if it is not a digit. 
        # End of string is also non-digit character.
        while index < n and input[index].isdigit():
            digit = int(input[index])
            
            # Check overflow and underflow conditions. 
            if ((result > INT_MAX // 10) or (result == INT_MAX // 10 and digit > INT_MAX % 10)):
                # If integer overflowed return 2^31-1, otherwise if underflowed return -2^31.    
                return INT_MAX if sign == 1 else INT_MIN
            
            # Append current digit to the result.
            result = 10 * result + digit
            index += 1
        
        # We have formed a valid number without any overflow/underflow.
        # Return it after multiplying it with its sign.
        return sign * result

12. Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Given an integer, convert it to a roman numeral.

Example 1: Input: num = 3 Output: "III" Explanation: 3 is represented as 3 ones.

Example 2: Input: num = 58 Output: "LVIII" Explanation: L = 50, V = 5, III = 3.

Example 3: Input: num = 1994 Output: "MCMXCIV" Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

1 <= num <= 3999

Python
# time = space = O(1)
class Solution:
    def intToRoman(self, num: int) -> str:
        digits = [(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), 
                  (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), 
                  (5, "V"), (4, "IV"), (1, "I")]
        
        roman_digits = []
        # Loop through each symbol.
        for value, symbol in digits:
            # We don't want to continue looping if we're done.
            if num == 0: break
            count, num = divmod(num, value)
            # Append "count" copies of "symbol" to roman_digits.
            roman_digits.append(symbol * count)
        return "".join(roman_digits)
Python
# time = space = O(1)
class Solution:
    def intToRoman(self, num: int) -> str:
        thousands = ["", "M", "MM", "MMM"]
        hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
        tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
        ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
        return (thousands[num // 1000] + hundreds[num % 1000 // 100] 
               + tens[num % 100 // 10] + ones[num % 10])
Python
100//1000
Output
0

13. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used: * I can be placed before V (5) and X (10) to make 4 and 9. * X can be placed before L (50) and C (100) to make 40 and 90. * C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:
Input: s = "III"
Output: 3

Example 2:
Input: s = "IV"
Output: 4

Example 3:
Input: s = "IX"
Output: 9

Example 4:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints: * 1 <= s.length <= 15 * s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M'). * It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Python
def romanToInt(s: str) -> int:
    
    s   = s.strip()
        
    conv = {
                'I': 1,
                'V': 5,
                'X': 10,
                'L': 50,
                'C': 100,
                'D': 500,
                'M': 1000,
                'IV': 4,
                'IX': 9,
                'XL': 40,
                'XC': 90,
                'CD': 400,
                'CM': 900,
            }
    
    res = 0
    i = 0
    while i < len(s):
        if s[i:i+2] in conv:
            res += conv[ s[i:i+2] ]
            i += 2
        else:
            res += conv[ s[i] ]
            i += 1
        
    return res


def romanToInt2(s: str) -> int:
    '''
        Leetcode solution - runs a bit faster
    '''
    
    values = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }
    
    total = 0
    i = 0
    while i < len(s):        
        if i+1 < len(s) and values[ s[i] ] < values[ s[i+1] ]:                   # subtractive case ('IX')
            total += values[ s[i+1] ] - values[ s[i] ]
            i += 2
        else:
            total += values[s[i]]
            i += 1
                        
    return total

    
s1 = 'III'
s2 = 'IV'
s3 = 'IX'
s4 = 'LVII'
s5 = 'MCMXCIV'

for s in [s1, s2, s3, s4, s5]:
    print( romanToInt(s) )
    
for s in [s1, s2, s3, s4, s5]:
    print( romanToInt2(s) )
Output
3
4
9
57
1994
3
4
9
57
1994

18. 4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

Python
# recursive ksum (any k)
# time = O(n^(k−1)), or O(n^3) for 4Sum, space = O(n)
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:

        def kSum(nums: List[int], target: int, k: int) -> List[List[int]]:
            res = []
            
            # If we have run out of numbers to add, return res.
            if not nums:
                return res
            
            # There are k remaining values to add to the sum. The 
            # average of these values is at least target // k.
            average_value = target // k
            
            # We cannot obtain a sum of target if the smallest value
            # in nums is greater than target // k or if the largest 
            # value in nums is smaller than target // k.
            if average_value < nums[0] or nums[-1] < average_value:
                return res
            
            if k == 2:
                return twoSum(nums, target)
    
            for i in range(len(nums)):
                if i == 0 or nums[i - 1] != nums[i]:
                    for subset in kSum(nums[i + 1:], target - nums[i], k - 1):
                        res.append([nums[i]] + subset)
    
            return res

        def twoSum(nums: List[int], target: int) -> List[List[int]]:
            res = []
            lo, hi = 0, len(nums) - 1
    
            while (lo < hi):
                curr_sum = nums[lo] + nums[hi]
                if curr_sum < target or (lo > 0 and nums[lo] == nums[lo - 1]):
                    lo += 1
                elif curr_sum > target or (hi < len(nums) - 1 and nums[hi] == nums[hi + 1]):
                    hi -= 1
                else:
                    res.append([nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                                                         
            return res

        nums.sort()
        return kSum(nums, target, 4)
Python
# hash set
# time = O(n^(k−1)), or O(n^3) for 4Sum, space = O(n)
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:

        def kSum(nums: List[int], target: int, k: int) -> List[List[int]]:
            res = []
            
            # If we have run out of numbers to add, return res.
            if not nums:
                return res
            
            # There are k remaining values to add to the sum. The 
            # average of these values is at least target // k.
            average_value = target // k
            
            # We cannot obtain a sum of target if the smallest value
            # in nums is greater than target // k or if the largest 
            # value in nums is smaller than target // k.
            if average_value < nums[0] or nums[-1] < average_value:
                return res
            
            if k == 2:
                return twoSum(nums, target)
    
            for i in range(len(nums)):
                if i == 0 or nums[i - 1] != nums[i]:
                    for subset in kSum(nums[i + 1:], target - nums[i], k - 1):
                        res.append([nums[i]] + subset)
    
            return res

        def twoSum(nums: List[int], target: int) -> List[List[int]]:
            res = []
            s = set()
    
            for i in range(len(nums)):
                if len(res) == 0 or res[-1][1] != nums[i]:
                    if target - nums[i] in s:
                        res.append([target - nums[i], nums[i]])
                s.add(nums[i])
    
            return res

        nums.sort()
        return kSum(nums, target, 4)

54. Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1: image.png Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5]

Example 2: image-2.png Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100

Hint #1
Well for some problems, the best way really is to come up with some algorithms for simulation. Basically, you need to simulate what the problem asks us to do.
Hint #2
We go boundary by boundary and move inwards. That is the essential operation. First row, last column, last row, first column, and then we move inwards by 1 and repeat. That's all. That is all the simulation that we need.
Hint #3
Think about when you want to switch the progress on one of the indexes. If you progress on i out of [i, j], you'll shift in the same column. Similarly, by changing values for j, you'd be shifting in the same row. Also, keep track of the end of a boundary so that you can move inwards and then keep repeating. It's always best to simulate edge cases like a single column or a single row to see if anything breaks or not.

Python
# set up boundaries
# time = O(MN), space = O(1)
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        result = []
        rows, columns = len(matrix), len(matrix[0])
        up = left = 0
        right = columns - 1
        down = rows - 1

        while len(result) < rows * columns:
            # Traverse from left to right.
            for col in range(left, right + 1):
                result.append(matrix[up][col])

            # Traverse downwards.
            for row in range(up + 1, down + 1):
                result.append(matrix[row][right])

            # Make sure we are now on a different row.
            if up != down:
                # Traverse from right to left.
                for col in range(right - 1, left - 1, -1):
                    result.append(matrix[down][col])

            # Make sure we are now on a different column.
            if left != right:
                # Traverse upwards.
                for row in range(down - 1, up, -1):
                    result.append(matrix[row][left])

            left += 1
            right -= 1
            up += 1
            down -= 1

        return result
Python
# mark visited elements
# time = O(MN), space = O(1)
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        VISITED = 101
        rows, columns = len(matrix), len(matrix[0])
        # Four directions that we will move: right, down, left, up.
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        # Initial direction: moving right.
        current_direction = 0
        # The number of times we change the direction.
        change_direction = 0
        # Current place that we are at is (row, col).
        # row is the row index; col is the column index.
        row = col = 0
        # Store the first element and mark it as visited.
        result = [matrix[0][0]]
        matrix[0][0] = VISITED

        while change_direction < 2:

            while True:
                # Calculate the next place that we will move to.
                next_row = row + directions[current_direction][0]
                next_col = col + directions[current_direction][1]

                # Break if the next step is out of bounds.
                if not (0 <= next_row < rows and 0 <= next_col < columns):
                    break
                # Break if the next step is on a visited cell.
                if matrix[next_row][next_col] == VISITED:
                    break

                # Reset this to 0 since we did not break and change the direction.
                change_direction = 0
                # Update our current position to the next step.
                row, col = next_row, next_col
                result.append(matrix[row][col])
                matrix[row][col] = VISITED

            # Change our direction.
            current_direction = (current_direction + 1) % 4
            # Increment change_direction because we changed our direction.
            change_direction += 1

        return result

229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Example 1: Input: nums = [3,2,3] Output: [3]

Example 2: Input: nums = [1] Output: [1]

Example 3: Input: nums = [1,2] Output: [1,2]

Constraints:

1 <= nums.length <= 5 * 10^4 -10^9 <= nums[i] <= 10^9

Follow up: Could you solve the problem in linear time and in O(1) space?

Hint #1
How many majority elements could it possibly have? Only 2 because three elements cannot each have count > n/3

Python
# Boyer-Moore Voting Algorithm
# time = O(n), space = O(1)
class Solution:

    def majorityElement(self, nums):
        if not nums:
            return []
        
        # 1st pass
        count1, count2, candidate1, candidate2 = 0, 0, None, None
        for n in nums:
            if candidate1 == n:
                count1 += 1
            elif candidate2 == n:
                count2 += 1
            elif count1 == 0:
                candidate1 = n
                count1 += 1
            elif count2 == 0:
                candidate2 = n
                count2 += 1
            else:
                count1 -= 1
                count2 -= 1
        
        # 2nd pass
        result = []
        for c in [candidate1, candidate2]:
            if nums.count(c) > len(nums)//3:
                result.append(c)

        return result

311. Sparse Matrix Multiplication

Given two sparse matrices mat1 of size m x k and mat2 of size k x n, return the result of mat1 x mat2. You may assume that multiplication is always possible.

Example 1: image.png Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]] Output: [[7,0,0],[-7,0,3]]

Example 2:

Input: mat1 = [[0]], mat2 = [[0]] Output: [[0]]

Constraints:

m == mat1.length k == mat1[i].length == mat2.length n == mat2[i].length 1 <= m, n, k <= 100 -100 <= mat1[i][j], mat2[i][j] <= 100

Yale Matrix Compression image-2.png

Algo image-3.png

Python
# Yale format
# time = O(m⋅n⋅k) where mat1.shape=[m,n], mat2.shape=[n,k]; space = O(m⋅k+k⋅n)
class SparseMatrix:
    def __init__(self, matrix: List[List[int]], col_wise: bool):
        self.values, self.row_index, self.col_index = self.compress_matrix(matrix, col_wise)

    def compress_matrix(self, matrix: List[List[int]], col_wise: bool):
        return self.compress_col_wise(matrix) if col_wise else self.compress_row_wise(matrix)

    # Compressed Sparse Row
    def compress_row_wise(self, matrix: List[List[int]]):
        values = []
        row_index = [0]
        col_index = []

        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if matrix[row][col]:
                    values.append(matrix[row][col])
                    col_index.append(col)
            row_index.append(len(values))

        return values, row_index, col_index

    # Compressed Sparse Column
    def compress_col_wise(self, matrix: List[List[int]]):
        values = []
        row_index = []
        col_index = [0]

        for col in range(len(matrix[0])):
            for row in range(len(matrix)):
                if matrix[row][col]:
                    values.append(matrix[row][col])
                    row_index.append(row)
            col_index.append(len(values))

        return values, row_index, col_index

class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
            A = SparseMatrix(mat1, False)
            B = SparseMatrix(mat2, True)
            
            ans = [[0] * len(mat2[0]) for _ in range(len(mat1))]

            for row in range(len(ans)):
                for col in range(len(ans[0])):

                    # Row element range indices
                    mat1_row_start = A.row_index[row]
                    mat1_row_end = A.row_index[row + 1]

                    # Column element range indices
                    mat2_col_start = B.col_index[col]
                    mat2_col_end = B.col_index[col + 1]
                    
                    # Iterate over both row and column.
                    while mat1_row_start < mat1_row_end and mat2_col_start < mat2_col_end:
                        if A.col_index[mat1_row_start] < B.row_index[mat2_col_start]:
                            mat1_row_start += 1
                        elif A.col_index[mat1_row_start] > B.row_index[mat2_col_start]:
                            mat2_col_start += 1
                        # Row index and col index are same so we can multiply these elements.
                        else:
                            ans[row][col] += A.values[mat1_row_start] * B.values[mat2_col_start]
                            mat1_row_start += 1
                            mat2_col_start += 1
    
            return ans
Python
# list of lists
# time = O(m⋅n⋅k) where mat1.shape=[m,n], mat2.shape=[n,k]; space = O(m⋅k+k⋅n)
class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        def compress_matrix(matrix: List[List[int]]) -> List[List[int]]:
            rows, cols = len(matrix), len(matrix[0])
            compressed_matrix = [[] for _ in range(rows)]
            for row in range(rows):
                for col in range(cols):
                    if matrix[row][col]:
                        compressed_matrix[row].append([matrix[row][col], col])
            return compressed_matrix
        
        m = len(mat1)
        k = len(mat1[0])
        n = len(mat2[0])
        
        # Store the non-zero values of each matrix.
        A = compress_matrix(mat1)
        B = compress_matrix(mat2)
        
        ans = [[0] * n for _ in range(m)]
        
        for mat1_row in range(m):
            # Iterate on all current 'row' non-zero elements of mat1.
            for element1, mat1_col in A[mat1_row]:
                # Multiply and add all non-zero elements of mat2
                # where the row is equal to col of current element of mat1.
                for element2, mat2_col in B[mat1_col]:
                    ans[mat1_row][mat2_col] += element1 * element2
                    
        return ans
Python
# naive
# time = O(m⋅n⋅k) where mat1.shape=[m,n], mat2.shape=[n,k]; space = O(1)
class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        
        # Product matrix.
        ans = [[0] * len(mat2[0]) for _ in range(len(mat1))]
        
        for row_index, row_elements in enumerate(mat1):
            for element_index, row_element in enumerate(row_elements):
                # If current element of mat1 is non-zero then iterate over all columns of mat2.
                if row_element:
                    for col_index, col_element in enumerate(mat2[element_index]):
                        ans[row_index][col_index] += row_element * col_element
        
        return ans

Linked Lists

These are some of the most important linked list questions asked by Apple. We recommend you practice all of these questions. One of the classics is Reverse Linked List. See all three questions in the above list of questions listed in other companies' notebooks

2. Add Two Numbers (Editor's choice: frequently asked by Apple) (F)

Two non-empty linked lists, one digit per node, represent two non-negative integers in reverse order. Add the two numbers, return sum as a reversed linked list. No leading zero, except the number 0 itself

image.png

Example 1: Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.

Example 2: Input: l1 = [0], l2 = [0] Output: [0]

Example 3: Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]

Constraints: * The number of nodes in each linked list is in the range [1, 100]. * 0 <= Node.val <= 9 * It is guaranteed that the list represents a number that does not have leading zeros EXCEPT FOR NUMBER 0 ITSELF

Python
class Node:    
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def addTwoNumbers(l1: Optional[Node], l2: Optional[Node]) -> Optional[Node]:
    '''
        My accepted optimized solution - replicates manual "columnar" addition. In line with Leetcode solution
        Time c. = space c. = O(max(m,n))
        Leetcode has a dummy_node = Node(0) as starting point, then assigns .next inside just one loop,
        and returns summy_node.next
    '''
    
    # edge cases    
    if not l1.next and l1.val == 0:
        return l2
    
    if not l2.next and l2.val == 0:
        return l1
        
    # iterate until one of the lists ends    
    new_nodes = []
    carry = 0
    while l1 or l2:
        sum_ = carry
        if l1: sum_ += l1.val                                     # in case on of the lists is shorter
        if l2: sum_ += l2.val        
        carry = sum_//10                                          # 0 if sum_ < 10
        new_nodes.append( Node(val=sum_%10) )
        
        if l1: l1 = l1.next
        if l2: l2 = l2.next    
        
    # see if carry is still non-zero
    if carry != 0:
        new_nodes.append( Node(val=carry) )
       
    # point nodes to each other successively (alternatively, use dummy_node = Node(0) as starting point
    # to avoid this loop and assign curr.next inside one main loop above)
    for i in range( len(new_nodes)-1 ):
        new_nodes[i].next = new_nodes[i+1]
       
    # return head
    return new_nodes[0]

    
# Output: [7,0,8]
l1 = [2,4,3],
l2 = [5,6,4]
n1 = Node(val=2)
n2 = Node(val=4)
n3 = Node(val=3)
n1.next = n2
n2.next = n3

n4 = Node(val=5)
n5 = Node(val=6)
n6 = Node(val=4)
n4.next = n5
n5.next = n6

n_new = addTwoNumbers(n1, n4)
n_new
Output
<__main__.Node at 0x7fbbc0dd1b50>

21. Merge Two Sorted Lists (Editor's choice: frequently asked by Apple) (F)

Merge two sorted non-decreasing linked lists, return sorted list by splicing together nodes of the first two lists

Example 1: Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2: Input: l1 = [], l2 = [] Output: []

Example 3: Input: l1 = [], l2 = [0] Output: [0]

Constraints: * The number of nodes in both lists is in the range [0, 50]. * -100 <= Node.val <= 100 * Both l1 and l2 are sorted in non-decreasing order

Python
class ListNode:    
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
                
        
def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    '''
        Leetcode solution
        Time c. O(n+m), space c. O(1)       
    '''
    # reference to return node (prehead will be disregarded as it's a singly linked list + head is returned)
    prehead = ListNode(-1)
    prev = prehead

    while l1 and l2:
        if l1.val <= l2.val:
            prev.next = l1                                   # assign entire node, NOT ListNode( l1.val )!
            l1 = l1.next
        else:
            prev.next = l2
            l2 = l2.next            
        prev = prev.next

    # One of l1 or l2 can still have nodes => connect
    # the non-null list to the end of merged list AND no need to iterate to the end!!!!!!
    prev.next = l1 if l1 else l2                 

    return prehead.next


l1 = [1,2,4]
l2 = [1,3,4]
n1 = Node(val=1)
n2 = Node(val=2)
n3 = Node(val=4)
n1.next = n2
n2.next = n3

n4 = Node(val=1)
n5 = Node(val=3)
n6 = Node(val=4)
n4.next = n5
n5.next = n6

n_new = mergeTwoLists(n1, n4)
n_new
Output
<__main__.Node at 0x7fba1307e650>
Python
while n_new:
    print(n_new.val, end=' ')
    n_new = n_new.next
Output
1 1 2 3 4 4

206. Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1: image.png Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

Example 2: image-2.png Input: head = [1,2] Output: [2,1]

Example 3:

Input: head = [] Output: []

Constraints:

The number of nodes in the list is the range [0, 5000]. -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Python
# time = O(n), space = O(1)
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
            
        return prev

Trees and Graphs

Apple likes to ask questions related to the Tree data structure. Even though graph-like questions are not frequently asked, definitely brush up on your graph fundamentals -- the "Clone Graph" problem is common in Apple interviews

133. Clone Graph (frequently asked by Apple)

Given reference of a node, always the first node with val = 1, in a connected undirected graph, return a deep copy (clone) of the graph. Each node has a value (int) and a an list of neighbors.

Example 1: Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4) 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3) 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4) 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3)

Example 2: Input: adjList = [[]] Output: [[]] Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3: Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.

Example 4: Input: adjList = [[2],[1]] Output: [[2],[1]]

Constraints: * The number of nodes in the graph is in the range [0, 100]. * 1 <= Node.val <= 100 * Node.val is unique for each node. * There are no repeated edges and no self-loops in the graph. * The Graph is connected and all nodes can be visited starting from the given node.

Solution: DFS or BFS when visited is actually a dict[curr_node] = cloned_node

Python
# Definition for a Node.
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

        
def cloneGraph(start: Node) -> Node:                
    if not start:
        return start

    visited, q = {}, [start]                                   # Dict[visited node] = its clone, to avoid cycles
    visited[start] = Node(start.val, [])                       # Clone it, put into visited

    while q:
        vertex = q.pop(0)                                      # get node            
        for neighbor in vertex.neighbors:                      # Iterate neighbors
            if neighbor not in visited:
                visited[neighbor] = Node(neighbor.val, [])     # Clone them, put into visited
                q.append(neighbor)                
            visited[vertex].neighbors.append(visited[neighbor])     # Add clone of neighbor to clone's neighbors

    return visited        # return visited[node] in the classical case
Python
# create graph from adjacency list
g = [[2,4],[1,3],[2,4],[1,3]]
graph = []
for idx, item in enumerate(g):
    graph.append( Node(val=idx+1) )
    
for idx, item in enumerate(graph):
    idxs = g[idx]
    item.neighbors = [graph[idxs[0]-1], graph[idxs[1]-1]]
    
# clone graph
visited = cloneGraph(graph[0])

# verify if cloned correctly
print('THE ORIGINAL:')
for vertex in visited:
    print(vertex.val)
    for neighbor in vertex.neighbors:
        print('\t', neighbor.val)

print('CLONE:')
for vertex in visited:
    clone = visited[vertex]
    print(clone.val)
    for neighbor in clone.neighbors:
        print('\t', neighbor.val)
Output
THE ORIGINAL:
1
	 2
	 4
2
	 1
	 3
4
	 1
	 3
3
	 2
	 4
CLONE:
1
	 2
	 4
2
	 1
	 3
4
	 1
	 3
3
	 2
	 4

200. Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1: Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1

Example 2: Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3

Constraints: * m == grid.length * n == grid[i].length * 1 <= m, n <= 300 * grid[i][j] is '0' or '1'

Brief solution from Discussion. Didn't have time to go over it

Python
from typing import List

def numIslands(grid: List[List[str]]) -> int:
    def sink(i, j):
        if 0 <= i < len(grid) and 0 <= j < len(grid[i]) and grid[i][j] == '1':
            grid[i][j] = '0'
            list(map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1)))
            return 1
        return 0
    return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))
Python
grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]
numIslands(grid)
Output
1

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes. Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Example 2: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3: Input: root = [1,2], p = 1, q = 2 Output: 1

Constraints: * The number of nodes in the tree is in the range [2, 10^5]. * -10^9 <= Node.val <= 10^9 * All Node.val are unique. * p != q * p and q will exist in the tree.

Below is a solution from my notebook (accepted by LeetCode; simpler than any of the 4 LeetCode solutions: * Time c. O(N) - visiting all N nodes in the worst case * Space c. O(N) - skewed binary tree with height N => parent pointer dictionary and the ancestor set would be N long each

Example in code below: image.png

Python
# Definition for a binary tree node
class Node:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

        
def lca(root, p, q):
    """
    SIMPLER THAN ANY LEETCODE SOLUTION
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    if not root or root is p or root is q:         # base case; NOT ROOT - reached end of tree
        return root                                # root is p/q - reached p/q

    left = lca(root.left, p, q)
    right = lca(root.right, p, q)

    if left and right:                            # this is lca
        return root

    return left if left else right                # p,q are both on one side of the tree
Python
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
Python
print(f"LCA(4, 5) = {lca(root, root.left.left, root.left.right,).val}")
print(f"LCA(4, 6) = {lca(root, root.left.left, root.right.left,).val}")
print(f"LCA(3, 4) = {lca(root, 3, 4,)}")
print(f"LCA(2, 4) = {lca(root, root.left, root.left.left,).val}")
Output
LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = None
LCA(2, 4) = 2

329. Longest Increasing Path in a Matrix

Given an m x n integers matrix, return the length of the longest increasing path in matrix.From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Example 1: image.png Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2: image-2.png Input: matrix = [[3,4,5],[3,2,6],[2,2,1]] Output: 4 Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3: Input: matrix = [[1]] Output: 1

Constraints:

m == matrix.length n == matrix[i].length 1 <= m, n <= 200 0 <= matrix[i][j] <= 231 - 1

Python
# Java
# DFS + Memoization Solution
# Accepted and Recommended
# time = O(mn). Each vertex/cell will be calculated once and only once, and each edge will be visited once
# and only once. The total time complexity is then O(V+E). V is the total number of vertices and E is
# the total number of edges. In our problem, O(V) = O(mn), O(E) = O(4V) = O(mn)
# space = O(mn), the cache dominates the space complexity
public class Solution {
    private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0;
        m = matrix.length; n = matrix[0].length;
        int[][] cache = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                ans = Math.max(ans, dfs(matrix, i, j, cache));
        return ans;
    }

    private int dfs(int[][] matrix, int i, int j, int[][] cache) {
        if (cache[i][j] != 0) return cache[i][j];
        for (int[] d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
                cache[i][j] = Math.max(cache[i][j], dfs(matrix, x, y, cache));
        }
        return ++cache[i][j];
    }
}

543. Diameter of Binary Tree

Return the length of the diameter of a binary tree = length of the longest path between any two nodes (may or may not pass through root). Length of a path = num edges

Example 1: Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2: Input: root = [1,2] Output: 1

Constraints: * The number of nodes in the tree is in the range [1, 10^4]. * -100 <= Node.val <= 100

Complexity * Time c. O(N). This is because in our recursion function longestPath, we only enter and exit from each node once. We know this because each node is entered from its parent, and in a tree, nodes only have one parent. * Space c. O(N). The space complexity depends on the size of our implicit call stack during our DFS, which relates to the height of the tree. In the worst case, the tree is skewed so the height of the tree is O(N)O(N). If the tree is balanced, it'd be O(\log N)O(logN).

Python
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def diameterOfBinaryTree(root: TreeNode) -> int:        

    def longest_path(node):

        if not node:
            return 0

        nonlocal diameter

        left_path  = longest_path(node.left)                                # longest path in left & right child
        right_path = longest_path(node.right)

        diameter = max(diameter, left_path + right_path)               # update if left_path + right_path > diam.

        return max(left_path, right_path) + 1                              # add 1 for connection to parent

    diameter = 0
    longest_path(root)

    return diameter
Python
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

diameterOfBinaryTree(root)
Output
4

100. Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1: image.png Input: p = [1,2,3], q = [1,2,3] Output: true

Example 2: image-2.png Input: p = [1,2], q = [1,null,2] Output: false

Example 3: image-3.png Input: p = [1,2,1], q = [1,1,2] Output: false

Constraints:

The number of nodes in both trees is in the range [0, 100]. -10^4 <= Node.val <= 10^4

Python
# recursive
# time = space = O(n)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """    
        # p and q are both None
        if not p and not q:
            return True
        # one of p and q is None
        if not q or not p:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.right, q.right) and \
               self.isSameTree(p.left, q.left)
Python
# iterative
# time = space = O(n)
from collections import deque
class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """    
        def check(p, q):
            # if both are None
            if not p and not q:
                return True
            # one of p and q is None
            if not q or not p:
                return False
            if p.val != q.val:
                return False
            return True
        
        deq = deque([(p, q),])
        while deq:
            p, q = deq.popleft()
            if not check(p, q):
                return False
            
            if p:
                deq.append((p.left, q.left))
                deq.append((p.right, q.right))
                    
        return True

104. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1: image.png Input: root = [3,9,20,null,null,15,7] Output: 3

Example 2: Input: root = [1,null,2] Output: 2

Constraints:

The number of nodes in the tree is in the range [0, 10^4]. -100 <= Node.val <= 100

Python
# recursive
# time = space = O(n) (space = O(logn) if tree is balanced => h = logn)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """ 
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1
Python
# iterative
# time = space = O(n) (space = O(logn) if tree is balanced => h = logn)
class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """ 
        stack = []
        if root is not None:
            stack.append((1, root))
        
        depth = 0
        while stack != []:
            current_depth, root = stack.pop()
            if root is not None:
                depth = max(depth, current_depth)
                stack.append((current_depth + 1, root.left))
                stack.append((current_depth + 1, root.right))
        
        return depth

Recursion

We recommend you complete all of these questions. These are some basic recursion questions asked by Apple. Practicing these problems will help you prepare for other interviews as well.

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. image.png A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1: Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2: Input: digits = "" Output: []

Example 3: Input: digits = "2" Output: ["a","b","c"]

Constraints:

0 <= digits.length <= 4 digits[i] is a digit in the range ['2', '9'].

Algorithm

As mentioned previously, we need to lock-in letters when we generate new letters. The easiest way to save state like this is to use recursion. Our algorithm will be as follows:

If the input is empty, return an empty array.

Initialize a data structure (e.g. a hash map) that maps digits to their letters, for example, mapping "6" to "m", "n", and "o".

Use a backtracking function to generate all possible combinations.

The function should take 2 primary inputs: the current combination of letters we have, path, and the index we are currently checking. As a base case, if our current combination of letters is the same length as the input digits, that means we have a complete combination. Therefore, add it to our answer, and backtrack. Otherwise, get all the letters that correspond with the current digit we are looking at, digits[index]. Loop through these letters. For each letter, add the letter to our current path, and call backtrack again, but move on to the next digit by incrementing index by 1. Make sure to remove the letter from path once finished with it.

Python
# time = O(N * (4^N)), where N = len of digits, space = O(n)
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # If the input is empty, immediately return an empty answer array
        if len(digits) == 0: 
            return []
        
        # Map all the digits to their corresponding letters
        letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", 
                   "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        
        def backtrack(index, path):
            # If the path is the same length as digits, we have a complete combination
            if len(path) == len(digits):
                combinations.append("".join(path))
                return # Backtrack
            
            # Get the letters that the current digit maps to, and loop through them
            possible_letters = letters[digits[index]]
            for letter in possible_letters:
                # Add the letter to our current path
                path.append(letter)
                # Move on to the next digit
                backtrack(index + 1, path)
                # Backtrack by removing the letter before moving onto the next
                path.pop()

        # Initiate backtracking with an empty path and starting index of 0
        combinations = []
        backtrack(0, [])
        return combinations
Python
# from comments
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        lookup = {
            "2": ["a", "b", "c"],
            "3": ["d", "e", "f"],
            "4": ["g", "h", "i"],
            "5": ["j", "k", "l"],
            "6": ["m", "n", "o"],
            "7": ["p", "q", "r", "s"],
            "8": ["t", "u", "v"],
            "9": ["w", "x", "y", "z"]
        }
        
        letter_lists = []
        for ch in digits:
            letter_lists.append(lookup[ch])
            
        while len(letter_lists) > 1:
            l1 = letter_lists.pop()
            l2 = letter_lists.pop()
            combos = []
            for i in l1:
                for j in l2:
                    combos.append(j + i)
            letter_lists.append(combos)
            
        return [] if not letter_lists else letter_lists[0]

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1: Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2: Input: n = 1 Output: ["()"]

Constraints:

1 <= n <= 8

Algorithm (backtracking)

Instead of adding '(' or ')' every time as in Approach 1, let's only add them when we know it will remain a valid sequence. We can do this by keeping track of the number of opening and closing brackets we have placed so far.

We can start an opening bracket if we still have one (of n) left to place. And we can start a closing bracket if it would not exceed the number of opening brackets.

Algorithm (closure number)

To enumerate something, generally we would like to express it as a sum of disjoint subsets that are easier to count.

Consider the closure number of a valid parentheses sequence S: the least index >= 0 so that S[0], S[1], ..., S[2*index+1] is valid. Clearly, every parentheses sequence has a unique closure number. We can try to enumerate them individually.

For each closure number c, we know the starting and ending brackets must be at index 0 and 2c + 1. Then, the 2c elements between must be a valid sequence, plus the rest of the elements must be a valid sequence

Python
# backtracking
# time = space = O((4^n)/sqrt(n))
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(S = [], left = 0, right = 0):
            if len(S) == 2 * n:
                ans.append("".join(S))
                return
            if left < n:
                S.append("(")
                backtrack(S, left+1, right)
                S.pop()
            if right < left:
                S.append(")")
                backtrack(S, left, right+1)
                S.pop()
        backtrack()
        return ans
Python
# closure number
# same complexity
class Solution(object):
    def generateParenthesis(self, N):
        if N == 0: return ['']
        ans = []
        for c in xrange(N):
            for left in self.generateParenthesis(c):
                for right in self.generateParenthesis(N-1-c):
                    ans.append('({}){}'.format(left, right))
        return ans

46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2: Input: nums = [0,1] Output: [[0,1],[1,0]]

Example 3: Input: nums = [1] Output: [[1]]

Constraints:

1 <= nums.length <= 6 -10 <= nums[i] <= 10 All the integers of nums are unique

Algorithm

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.

Here is a backtrack function which takes the index of the first integer to consider as an argument backtrack(first).

If the first integer to consider has index n that means that the current permutation is done. Iterate over the integers from index first to index n - 1. Place i-th integer first in the permutation, i.e. swap(nums[first], nums[i]). Proceed to create all permutations which starts from i-th integer : backtrack(first + 1). Now backtrack, i.e. swap(nums[first], nums[i]) back

Python
# time = O(∑(N,k=1) P(N,k)); where P(N,k)= N! / (N−k)! = N(N−1)...(N−k+1); O(N!)
class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first = 0):
            # if all integers are used up
            if first == n:  
                output.append(nums[:])
            for i in range(first, n):
                # place i-th integer first 
                # in the current permutation
                nums[first], nums[i] = nums[i], nums[first]
                # use next integers to complete the permutations
                backtrack(first + 1)
                # backtrack
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        output = []
        backtrack()
        return output
Python
# simpler, based on string permutation algo
def permute(nums):
    out = []
    if len(nums) == 1:
        out = [nums]
    else:
        for idx, num in enumerate(nums):
            for perm in permute(nums[:idx] + nums[idx+1:]):
                out.append([num] + perm)
    return out

nums = [1,2,3]
permute(nums)
Output
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

78. Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1: Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2: Input: nums = [0] Output: [[],[0]]

Constraints:

1 <= nums.length <= 10 -10 <= nums[i] <= 10 All the numbers of nums are unique

Algorithm

We define a backtrack function named backtrack(first, curr) which takes the index of first element to add and a current combination as arguments.

If the current combination is done, we add the combination to the final output.

Otherwise, we iterate over the indexes i from first to the length of the entire sequence n.

Add integer nums[i] into the current combination curr.

Proceed to add more integers into the combination : backtrack(i + 1, curr).

Backtrack by removing nums[i] from curr

Python
# time = O(N*(2^N)), space = O(N) where N = len(nums)
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first = 0, curr = []):
            # if the combination is done
            if len(curr) == k:  
                output.append(curr[:])
                return
            for i in range(first, n):
                # add nums[i] into the current combination
                curr.append(nums[i])
                # use next integers to complete the combination
                backtrack(i + 1, curr)
                # backtrack
                curr.pop()
        
        output = []
        n = len(nums)
        for k in range(n + 1):
            backtrack()
        return output

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1: image.png Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true

Example 2: image-2.png Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true

Example 3: image-3.png Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false

Constraints:

m == board.length n = board[i].length 1 <= m, n <= 6 1 <= word.length <= 15 board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Python
# time = O(N⋅3^L) where N = # cells in board and L = len of word to be matched; space = O(L)
class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        self.ROWS = len(board)
        self.COLS = len(board[0])
        self.board = board

        for row in range(self.ROWS):
            for col in range(self.COLS):
                if self.backtrack(row, col, word):
                    return True

        # no match found after all exploration
        return False


    def backtrack(self, row, col, suffix):
        # bottom case: we find match for each letter in the word
        if len(suffix) == 0:
            return True

        # Check the current status, before jumping into backtracking
        if row < 0 or row == self.ROWS or col < 0 or col == self.COLS \
                or self.board[row][col] != suffix[0]:
            return False

        ret = False
        # mark the choice before exploring further.
        self.board[row][col] = '#'
        # explore the 4 neighbor directions
        for rowOffset, colOffset in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            ret = self.backtrack(row + rowOffset, col + colOffset, suffix[1:])
            # break instead of return directly to do some cleanup afterwards
            if ret: break

        # revert the change, a clean slate and no side-effect
        self.board[row][col] = suffix[0]

        # Tried all directions, and did not find any match
        return ret

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1: Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

Example 2: Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]] Example 3: Input: candidates = [2], target = 1 Output: []

Constraints:

1 <= candidates.length <= 30 2 <= candidates[i] <= 40 All elements of candidates are distinct. 1 <= target <= 40

Python
# backtracking
# time = O(N^((T/M)+1), space = O(T/M)
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        results = []

        def backtrack(remain, comb, start):
            if remain == 0:
                # make a deep copy of the current combination
                results.append(list(comb))
                return
            elif remain < 0:
                # exceed the scope, stop exploration.
                return

            for i in range(start, len(candidates)):
                # add the number into the combination
                comb.append(candidates[i])
                # give the current number another chance, rather than moving on
                backtrack(remain - candidates[i], comb, i)
                # backtrack, remove the number from the combination
                comb.pop()

        backtrack(target, [], 0)

        return results
Python
# my solution - how does t. complexity compare w/Leetcode's
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    def backtrack(curr):
        if curr is None:
            return curr
        elif sum(curr) == target:
            curr = sorted(curr)
            if curr not in res:
                res.append(curr)
        elif sum(curr) > target:
            return None
        
        for cand in candidates:
            backtrack(curr + [cand])
        
    res = []
    backtrack([])
    return list(res)
Python
candidates = [2,3,5] #[2,3,6,7]
target = 8 #7
combinationSum(candidates, target)

Sorting and Searching

We highly recommend practicing the Intersection of Two Arrays problem, which is frequently asked in Apple's phone interview. See all questions from this section in the above list of questions from other companies' notebooks

56. Merge Intervals (Editor's choice: frequently asked by Apple)

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

1 <= intervals.length <= 104 intervals[i].length == 2 0 <= starti <= endi <= 104

Algorithm

First, we sort the list as described. Then, we insert the first interval into our merged list and continue considering each interval in turn as follows: If the current interval begins after the previous interval ends, then they do not overlap and we can append the current interval to merged. Otherwise, they do overlap, and we merge them by updating the end of the previous interval if it is less than the end of the current interval.

A simple proof by contradiction shows that this algorithm always produces the correct answer. First, suppose that the algorithm at some point fails to merge two intervals that should be merged. This would imply that there exists some triple of indices ii, jj, and kk in a list of intervals \text{ints}ints such that i < j < ki<j<k and (\text{ints[i]}ints[i], \text{ints[k]}ints[k]) can be merged, but neither (\text{ints[i]}ints[i], \text{ints[j]}ints[j]) nor (\text{ints[j]}ints[j], \text{ints[k]}ints[k]) can be merged. From this scenario follow several inequalities:

\begin{aligned} \text{ints[i].end} < \text{ints[j].start} \ \text{ints[j].end} < \text{ints[k].start} \ \text{ints[i].end} \geq \text{ints[k].start} \ \end{aligned} ints[i].end<ints[j].start ints[j].end<ints[k].start ints[i].end≥ints[k].start ​

We can chain these inequalities (along with the following inequality, implied by the well-formedness of the intervals: \text{ints[j].start} \leq \text{ints[j].end}ints[j].start≤ints[j].end) to demonstrate a contradiction:

\begin{aligned} \text{ints[i].end} < \text{ints[j].start} \leq \text{ints[j].end} < \text{ints[k].start} \ \text{ints[i].end} \geq \text{ints[k].start} \end{aligned} ints[i].end<ints[j].start≤ints[j].end<ints[k].start ints[i].end≥ints[k].start ​

Therefore, all mergeable intervals must occur in a contiguous run of the sorted list.

Python
# Leetcode solution - time = O(nlogn), space = O(logn)
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals.sort(key=lambda x: x[0])

        merged = []
        for interval in intervals:
            # if the list of merged intervals is empty or if the current
            # interval does not overlap with the previous, simply append it.
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
            # otherwise, there is overlap, so we merge the current and previous
            # intervals.
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

349. Intersection of Two Arrays (Editor's choice: frequently asked by Apple) (F)

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

Approach 1: Two Sets

The naive approach would be to iterate along the first array nums1 and to check for each value if this value in nums2 or not. If yes - add the value to output. Such an approach would result in a pretty bad \mathcal{O}(n \times m)O(n×m) time complexity, where n and m are arrays' lengths.

To solve the problem in linear time, let's use the structure set, which provides in/contains operation in O(1) time in average case.

The idea is to convert both arrays into sets, and then iterate over the smallest set checking the presence of each element in the larger set. Time complexity of this approach is O(n+m) in the average case.

Complexity Analysis for Approach 1

Time complexity: O(n+m), where n and m are arrays' lengths. O(n) time is used to convert nums1 into set, O(m) time is used to convert nums2, and contains/in operations are O(1) in the average case.

Space complexity: O(m+n) in the worst case when all elements in the arrays are different.

Approach 2: Built-in Set Intersection

There are built-in intersection facilities, which provide O(n+m) time complexity in the average case and O(n×m) time complexity in the worst case

Python
# Approach 1
# time = O(n+m), space = O(n+m)
class Solution:
    def set_intersection(self, set1, set2):
        return [x for x in set1 if x in set2]
        #return list(set2 & set1)
        
    def intersection(self, nums1, nums2):
        set1 = set(nums1)
        set2 = set(nums2)
        
        if len(set1) < len(set2):
            return self.set_intersection(set1, set2)
        else:
            return self.set_intersection(set2, set1)

        
# My similar solution: time = O(n+m), space = O(n+m) NO NEED TO SEE WHICH ONE IS LONGER - INTERSECT IS IN BOTH SETS!
def intersection(nums1, nums2):
    nums1 = set(nums1)
    nums2 = set(nums2)
    return [i for i in nums1 if i in nums2]
Python
nums1 = [2,2]
nums2 = [1,2,2,1]
print(intersection(nums1, nums2))

nums1 = [5,9,6]
nums2 = [9,5,9,8,5]
print(intersection(nums1, nums2))
Output
[2]
[9, 5]

4. Median of Two Sorted Arrays (no official solution)

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.

Example 2: Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106

No official solution on Leetcode (see comments)

Python
# t. O(m+n), s. O(1)
from typing import List
def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
    if(len(nums1) > len(nums2)):
        return findMedianSortedArrays(nums2, nums1)
    array_1 = nums1
    array_2 = nums2
    start = 0
    end = len(array_1)
    X = len(array_1)
    Y = len(array_2)
    while(start <= end):

        partitionX = int((start + end )/2)
        partitionY = int((X + Y + 1 )/2 - partitionX)

#Edge case when there is nothing on the left side, then we assign x1 to infinity
        if (partitionX == 0):
            X1 = float('-inf')
        else:
            X1 = array_1[partitionX - 1]

        if (partitionX == len(array_1) ):
            X2 = float('inf')
        else:
            X2 = array_1[partitionX]

        if (partitionY == 0):
            Y1 = float('-inf')
        else:
            Y1 = array_2[partitionY - 1]

        if (partitionY == len(array_2) ):
            Y2 = float('inf')
        else:
            Y2 = array_2[partitionY]
        if ((X1 <= Y2) and (Y1 <= X2)):

            # We have found correct partitions

            #Check if the sum of length of both is odd or even

            if( (X+Y) % 2 == 0):

                median = ((max(X1,Y1) + min(X2, Y2))/2)
                return median
            else:

                median = max(X1,Y1)
                return median

        elif(Y1 > X2):
            start = partitionX + 1
        else:
            end = partitionX - 1
Python
nums1 = [1,3]
nums2 = [2]
findMedianSortedArrays(nums1, nums2)
Output
2

33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Example 2: Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

Example 3: Input: nums = [1], target = 0 Output: -1

Constraints:

1 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4 All values of nums are unique. nums is an ascending array that is possibly rotated. -10^4 <= target <= 10^4

Algorithm (binary search in one pass)

As in the normal binary search, we keep two pointers (i.e. start and end) to track the search scope. At each iteration, we reduce the search scope into half, by moving either the start or end pointer to the middle (i.e. mid) of the previous search scope.

Here are the detailed breakdowns of the algorithm:

Initiate the pointer start to 0, and the pointer end to n - 1.

Perform standard binary search. While start <= end:

Take an index in the middle mid as a pivot.

If nums[mid] == target, the job is done, return mid.

Now there could be two situations:

Pivot element is larger than the first element in the array, i.e. the subarray from the first element to the pivot is non-rotated, as shown in the following graph. pic

We're here because the target is not found. Return -1.

Python
# time = O(logn), space = O(1)
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] >= nums[start]:
                if target >= nums[start] and target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            else:
                if target <= nums[end] and target > nums[mid]:
                    start = mid + 1
                else:
                    end = mid - 1
        return -1

242. Valid Anagram (strings notebook)

Check if anagrams

Anagrams share exact same characters (rearranged and ignoring spaces / capitalization)

Python
# not optimal
def anagram_check(s1, s2):
    
    # remove spaces and make lowercase
    s1 = s1.replace(' ','').lower()
    s2 = s2.replace(' ','').lower()
        
    return sorted(s1) == sorted(s2)


# O(N)
def anagram_check2(s1, s2):
    
    # remove spaces and lowercase letters
    s1 = s1.replace(' ','').lower()
    s2 = s2.replace(' ','').lower()
    
    # edge case
    if len(s1) != len(s2):
        return False
    
    # counting dict (or defaultdict())
    count = {}    
    
        
    # iterate over first string (ADD counts)
    for char in s1:
        if char in count:
            count[char] += 1
        else:
            count[char] = 1
            
    # iterate over second string (SUBSTRACT counts)
    for char in s2:
        if char in count:
            count[char] -= 1
        else:
            count[char] = 1
    
    # check if all are 0
    for k in count:
        if count[k] != 0:
            return False
    
    return True
Python
anagrams = [('public relations', 'crap built on lies'), ('dog','god'), ('clint eastwood','old west action'), ('dd','aa')]

print('Using sort-based aproach:')
for a in anagrams:
    print('\t{} for "{}"'.format(anagram_check(*a), ' AND '.join(a)))
    
print('\nUsing counting aproach:')
for a in anagrams:
    print('\t{} for "{}"'.format(anagram_check2(*a), ' AND '.join(a)))
Output
Using sort-based aproach:
	True for "public relations AND crap built on lies"
	True for "dog AND god"
	True for "clint eastwood AND old west action"
	False for "dd AND aa"

Using counting aproach:
	True for "public relations AND crap built on lies"
	True for "dog AND god"
	True for "clint eastwood AND old west action"
	False for "dd AND aa"

350. Intersection of Two Arrays II

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear in any order as many times as it shows in the array where it is less frequent.

Note: on LeetCode, this is phrased: as many time as it shows in both arrays - which is incorrect

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted.

My solution below:
* Runtime: 64 ms, faster than 32.78% of Python3 online submissions for Intersection of Two Arrays II. * Memory Usage: 14.5 MB, less than 41.10% of Python3 online submissions for Intersection of Two Arrays II.

Python
# My solution: time c. O(n^2)
def intersect(nums1: List[int], nums2: List[int]) -> List[int]:
        
        res = []
        common = set(nums1).intersection(set(nums2))               # O(n+m)
        for i in common:
            count = min(nums1.count(i), nums2.count(i))            # O(n*(n+m))
            res.extend([i]*count)                                  # O(1) or O(n) dep. on if you need to copy array
        
        return res                                                 # O(n^2)
Python
# LeetCode solution 1: time c. O(n+m)
def intersect2(nums1: List[int], nums2: List[int]) -> List[int]:
    
    if len(nums1) > len(nums2):
        return intersect(nums2, nums1)

    mapp = defaultdict(int)
    for n in nums1:
        mapp[n] += 1

    k = 0
    for n in nums2:
        if n in mapp and mapp[n] > 0:
            nums1[k] = n
            k += 1
            mapp[n] -= 1

    return nums1[:k+1]
Python
nums1 = [1,2,2,1,4,7]
nums2 = [2,2,7]
intersect2(nums1, nums2)
Output
[2, 2, 7]

973. K Closest Points to Origin

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0). The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2). You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1: image.png Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Example 2: Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Constraints: 1 <= k <= points.length <= 10^4 -104 < xi, yi < 10^4

Algorithm

Let's do the work(i, j, K) of partially sorting the subarray (points[i], points[i+1], ..., points[j]) so that the smallest K elements of this subarray occur in the first K positions (i, i+1, ..., i+K-1).

First, we quickselect by a random pivot element from the subarray. To do this in place, we have two pointers i and j, and move these pointers to the elements that are in the wrong bucket -- then, we swap these elements.

After, we have two buckets [oi, i] and [i+1, oj], where (oi, oj) are the original (i, j) values when calling work(i, j, K). Say the first bucket has 10 items and the second bucket has 15 items. If we were trying to partially sort say, K = 5 items, then we only need to partially sort the first bucket: work(oi, i, 5). Otherwise, if we were trying to partially sort say, K = 17 items, then the first 10 items are already partially sorted, and we only need to partially sort the next 7 items: work(i+1, oj, 7).

Python
# time = space = O(N)
class Solution(object):
    def kClosest(self, points, K):
        dist = lambda i: points[i][0]**2 + points[i][1]**2

        def sort(i, j, K):
            # Partially sorts A[i:j+1] so the first K elements are
            # the smallest K elements.
            if i >= j: return

            # Put random element as A[i] - this is the pivot
            k = random.randint(i, j)
            points[i], points[k] = points[k], points[i]

            mid = partition(i, j)
            if K < mid - i + 1:
                sort(i, mid - 1, K)
            elif K > mid - i + 1:
                sort(mid + 1, j, K - (mid - i + 1))

        def partition(i, j):
            # Partition by pivot A[i], returning an index mid
            # such that A[i] <= A[mid] <= A[j] for i < mid < j.
            oi = i
            pivot = dist(i)
            i += 1

            while True:
                while i < j and dist(i) < pivot:
                    i += 1
                while i <= j and dist(j) >= pivot:
                    j -= 1
                if i >= j: break
                points[i], points[j] = points[j], points[i]

            points[oi], points[j] = points[j], points[oi]
            return j

        sort(0, len(points) - 1, K)
        return points[:K]

75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example 1: Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

Example 2: Input: nums = [2,0,1] Output: [0,1,2]

Constraints:

n == nums.length 1 <= n <= 300 nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Hide Hint #1
A rather straight forward solution is a two-pass algorithm using counting sort. Hide Hint #2
Iterate the array counting number of 0's, 1's, and 2's. Hide Hint #3
Overwrite array with the total number of 0's, then 1's and followed by 2's.

Python
# time = O(N), space = O(1)
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Dutch National Flag problem solution.
        """
        # for all idx < p0 : nums[idx < p0] = 0
        # curr is an index of element under consideration
        p0 = curr = 0
        # for all idx > p2 : nums[idx > p2] = 2
        p2 = len(nums) - 1

        while curr <= p2:
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1

692. Top K Frequent Words

Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1: Input: words = ["i","love","leetcode","i","love","coding"], k = 2 Output: ["i","love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.

Example 2: Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4 Output: ["the","is","sunny","day"] Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

Constraints:

1 <= words.length <= 500 1 <= words[i].length <= 10 words[i] consists of lowercase English letters. k is in the range [1, The number of unique words[i]]

Follow-up: Could you solve it in O(n log(k)) time and O(n) extra space?

Python
# min heap
# time = O(Nlogk), space = O(N) where N = len(words)
from collections import Counter
from heapq import heappush, heappop


class Pair:
    def __init__(self, word, freq):
        self.word = word
        self.freq = freq

    def __lt__(self, p):
        return self.freq < p.freq or (self.freq == p.freq and self.word > p.word)


class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        cnt = Counter(words)
        h = []
        for word, freq in cnt.items():
            heappush(h, Pair(word, freq))
            if len(h) > k:
                heappop(h)
        return [p.word for p in sorted(h, reverse=True)]
Python
# max heap
# time = O(N+klogN), space = O(N) where N = len(words)
from collections import Counter
from heapq import nsmallest

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        cnt = Counter(words)
        return nsmallest(k, cnt.keys(), key=lambda x: (-cnt[x], x))

Dynamic Programming

Apple does not ask a whole lot of Dynamic Programming questions. We recommend practicing the Best Time to Buy, the Sell Stock, and the Maximum Subarray problems.

53. Maximum Subarray (Editor's choice: frequently asked by Apple) (G)

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array.

Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2: Input: nums = [1] Output: 1

Example 3: Input: nums = [5,4,-1,7,8] Output: 23

Constraints:

1 <= nums.length <= 105 -104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Algorithm

Initialize 2 integer variables. Set both of them equal to the first value in the array.

currentSubarray will keep the running count of the current subarray we are focusing on. maxSubarray will be our final return value. Continuously update it whenever we find a bigger subarray. Iterate through the array, starting with the 2nd element (as we used the first element to initialize our variables). For each number, add it to the currentSubarray we are building. If currentSubarray becomes negative, we know it isn't worth keeping, so throw it away. Remember to update maxSubarray every time we find a new maximum.

Return maxSubarray

Python
# time = O(n), space = O(1)
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # Initialize our variables using the first element.
        current_subarray = max_subarray = nums[0]
        
        # Start with the 2nd element since we already used the first one.
        for num in nums[1:]:
            # If current_subarray is negative, throw it away. Otherwise, keep adding to it.
            current_subarray = max(num, current_subarray + num)
            max_subarray = max(max_subarray, current_subarray)
        
        return max_subarray

121. Best Time to Buy and Sell Stock (Editor's choice: frequently asked by Apple) (G)

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1: Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2: Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 105 0 <= prices[i] <= 104

Algorithm Say the given array is:

[7, 1, 5, 3, 6, 4] If we plot the numbers of the given array on a graph, we get: image.png Profit Graph

The points of interest are the peaks and valleys in the given graph. We need to find the largest price following each valley, which difference could be the max profit. We can maintain two variables - minprice and maxprofit corresponding to the smallest valley and maximum profit (maximum difference between selling price and minprice) obtained so far respectively.

Python
# time = O(n), space = O(1)
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for i in range(len(prices)):
            if prices[i] < min_price:
                min_price = prices[i]
            elif prices[i] - min_price > max_profit:
                max_profit = prices[i] - min_price
                
        return max_profit

5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s. A string is called a palindrome string if the reverse of that string is the same as the original string.

Example 1: Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.

Example 2: Input: s = "cbbd" Output: "bb"

Constraints:

1 <= s.length <= 1000 s consist of only digits and English letters.

Python
# Java
# time = O(n^2), space = O(1)
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }
}

10. Regular Expression Matching

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

'.' Matches any single character.​​​​ '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Example 1: Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa".

Example 2: Input: s = "aa", p = "a" Output: true Explanation: '' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3: Input: s = "ab", p = "." Output: true Explanation: "." means "zero or more (*) of any character (.)".

Constraints:

1 <= s.length <= 20 1 <= p.length <= 30 s contains only lowercase English letters. p contains only lowercase English letters, '.', and ''. It is guaranteed for each appearance of the character '', there will be a previous valid character to match

Algorithm

We proceed with the same recursion as in Approach 1, except because calls will only ever be made to match(text[i:], pattern[j:]), we use \text{dp(i, j)}dp(i, j) to handle those calls instead, saving us expensive string-building operations and allowing us to cache the intermediate results

Python
# DP top down
# time = space = O(TP) where T,P = len of text and pattern
class Solution(object):
    def isMatch(self, text, pattern):
        memo = {}
        def dp(i, j):
            if (i, j) not in memo:
                if j == len(pattern):
                    ans = i == len(text)
                else:
                    first_match = i < len(text) and pattern[j] in {text[i], '.'}
                    if j+1 < len(pattern) and pattern[j+1] == '*':
                        ans = dp(i, j+2) or first_match and dp(i+1, j)
                    else:
                        ans = first_match and dp(i+1, j+1)

                memo[i, j] = ans
            return memo[i, j]

        return dp(0, 0)
Python
# DP bottom up
class Solution(object):
    def isMatch(self, text, pattern):
        dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]

        dp[-1][-1] = True
        for i in range(len(text), -1, -1):
            for j in range(len(pattern) - 1, -1, -1):
                first_match = i < len(text) and pattern[j] in {text[i], '.'}
                if j+1 < len(pattern) and pattern[j+1] == '*':
                    dp[i][j] = dp[i][j+2] or first_match and dp[i+1][j]
                else:
                    dp[i][j] = first_match and dp[i+1][j+1]

        return dp[0][0]

139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1: Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2: Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3: Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false

Constraints:

1 <= s.length <= 300 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 20 s and wordDict[i] consist of only lowercase English letters. All the strings of wordDict are unique.

Algorithm (recursion w/memoization)

In the previous approach we can see that many subproblems were redundant, i.e we were calling the recursive function multiple times for a particular string. To avoid this we can use memoization method, where an array memomemo is used to store the result of the subproblems. Now, when the function is called again for a particular string, value will be fetched and returned using the memomemo array, if its value has been already evaluated.

With memoization many redundant subproblems are avoided and recursion tree is pruned and thus it reduces the time complexity by a large factor.

Algorithm (BFS)

Another approach is to use Breadth-First-Search. Visualize the string as a tree where each node represents the prefix upto index endend. Two nodes are connected only if the substring between the indices linked with those nodes is also a valid string which is present in the dictionary. In order to form such a tree, we start with the first character of the given string (say ss) which acts as the root of the tree being formed and find every possible substring starting with that character which is a part of the dictionary. Further, the ending index (say ii) of every such substring is pushed at the back of a queue which will be used for Breadth First Search. Now, we pop an element out from the front of the queue and perform the same process considering the string s(i+1,end)s(i+1,end) to be the original string and the popped node as the root of the tree this time. This process is continued, for all the nodes appended in the queue during the course of the process. If we are able to obtain the last element of the given string as a node (leaf) of the tree, this implies that the given string can be partitioned into substrings which are all a part of the given dictionary.

Algorithm (DP) image.png

Python
# recursion w/memoization
# time = O(n^3), space = O(n)
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        @lru_cache
        def wordBreakMemo(s: str, word_dict: FrozenSet[str], start: int):
            if start == len(s):
                return True
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in word_dict and wordBreakMemo(s, word_dict, end):
                    return True
            return False

        return wordBreakMemo(s, frozenset(wordDict), 0)
Python
# BFS
# time = O(n^3), space = O(n)
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        q = deque()
        visited = set()

        q.append(0)
        while q:
            start = q.popleft()
            if start in visited:
                continue
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in word_set:
                    q.append(end)
                    if end == len(s):
                        return True
            visited.add(start)
        return False
Python
# DP
# time = O(n^3), space = O(n)
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        dp = [False] * (len(s) + 1)
        dp[0] = True

        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break
        return dp[len(s)]

Design

These are some design questions for you to practice for your Apple interview. We highly recommend the LRU Cache problem. See all questions from this section in the above list of questions from other companies' notebooks

146. LRU Cache (Editor's choice: frequently asked by Apple) (G)

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity.

Example 1:

Input ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4

Constraints:

1 <= capacity <= 3000 0 <= key <= 104 0 <= value <= 105 At most 2 * 105 calls will be made to get and put

Intuition

We're asked to implement the structure which provides the following operations in \mathcal{O}(1)O(1) time :

Get the key / Check if the key exists

Put the key

Delete the first added key

The first two operations in O(1) time are provided by the standard hashmap, and the last one - by linked list

Python
class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
Python
from collections import OrderedDict
class LRUCache(OrderedDict):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self:
            return - 1
        
        self.move_to_end(key)
        return self[key]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last = False)
Python
# time = O(1), space = O(capacity)
class DLinkedNode(): 
    def __init__(self):
        self.key = 0
        self.value = 0
        self.prev = None
        self.next = None
            
class LRUCache():
    def _add_node(self, node):
        """
        Always add the new node right after head.
        """
        node.prev = self.head
        node.next = self.head.next

        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        """
        Remove an existing node from the linked list.
        """
        prev = node.prev
        new = node.next

        prev.next = new
        new.prev = prev

    def _move_to_head(self, node):
        """
        Move certain node in between to the head.
        """
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        """
        Pop the current tail.
        """
        res = self.tail.prev
        self._remove_node(res)
        return res

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cache = {}
        self.size = 0
        self.capacity = capacity
        self.head, self.tail = DLinkedNode(), DLinkedNode()

        self.head.next = self.tail
        self.tail.prev = self.head
        

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        node = self.cache.get(key, None)
        if not node:
            return -1

        # move the accessed node to the head;
        self._move_to_head(node)

        return node.value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        node = self.cache.get(key)

        if not node: 
            newNode = DLinkedNode()
            newNode.key = key
            newNode.value = value

            self.cache[key] = newNode
            self._add_node(newNode)

            self.size += 1

            if self.size > self.capacity:
                # pop the tail
                tail = self._pop_tail()
                del self.cache[tail.key]
                self.size -= 1
        else:
            # update the value.
            node.value = value
            self._move_to_head(node)

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.

Example 1:

Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

Output [null,null,null,null,-3,null,0,-2]

Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints:

-2^31 <= val <= 2^31 - 1 Methods pop, top and getMin operations will always be called on non-empty stacks. At most 3 * 104 calls will be made to push, pop, top, and getMin.

Python
# time = O(1), space = O(n)
class MinStack:

    def __init__(self):
        self.stack = []
        

    def push(self, x: int) -> None:
        
        # If the stack is empty, then the min value
        # must just be the first value we add
        if not self.stack:
            self.stack.append((x, x))
            return

        current_min = self.stack[-1][1]
        self.stack.append((x, min(x, current_min)))
        
        
    def pop(self) -> None:
        self.stack.pop()
        

    def top(self) -> int:
        return self.stack[-1][0]
        

    def getMin(self) -> int:
        return self.stack[-1][1]
Python
# time = O(1), space = O(n)
# different approach
class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []        
        

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
    
    def pop(self) -> None:
        if self.min_stack[-1] == self.stack[-1]:
            self.min_stack.pop()
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]
Python
# time = O(1), space = O(n)
# improved different approach
class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []        
        

    def push(self, x: int) -> None:
        
        # We always put the number onto the main stack.
        self.stack.append(x)
        
        # If the min stack is empty, or this number is smaller than
        # the top of the min stack, put it on with a count of 1.
        if not self.min_stack or x < self.min_stack[-1][0]:
            self.min_stack.append([x, 1])
            
        # Else if this number is equal to what's currently at the top
        # of the min stack, then increment the count at the top by 1.
        elif x == self.min_stack[-1][0]:
            self.min_stack[-1][1] += 1

    
    def pop(self) -> None:

        # If the top of min stack is the same as the top of stack
        # then we need to decrement the count at the top by 1.
        if self.min_stack[-1][0] == self.stack[-1]:
            self.min_stack[-1][1] -= 1
            
        # If the count at the top of min stack is now 0, then remove
        # that value as we're done with it.
        if self.min_stack[-1][1] == 0:
            self.min_stack.pop()
            
        # And like before, pop the top of the main stack.
        self.stack.pop()


    def top(self) -> int:
        return self.stack[-1]


    def getMin(self) -> int:
        return self.min_stack[-1][0]

380. Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object. bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned. You must implement the functions of the class such that each function works in average O(1) time complexity

Example 1:

Input ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Output [null, true, false, true, 2, true, false, 2]

Explanation RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2]. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

-231 <= val <= 231 - 1 At most 2 * 105 calls will be made to insert, remove, and getRandom. There will be at least one element in the data structure when getRandom is called.

Python
# time = O(1), space = O(n)
from random import choice
class RandomizedSet():
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dict = {}
        self.list = []

        
    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val in self.dict:
            return False
        self.dict[val] = len(self.list)
        self.list.append(val)
        return True
        

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val in self.dict:
            # move the last element to the place idx of the element to delete
            last_element, idx = self.list[-1], self.dict[val]
            self.list[idx], self.dict[last_element] = last_element, idx
            # delete the last element
            self.list.pop()
            del self.dict[val]
            return True
        return False

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        return choice(self.list)

341. Flatten Nested List Iterator

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

NestedIterator(List nestedList) Initializes the iterator with the nested list nestedList. int next() Returns the next integer in the nested list. boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise. Your code will be tested with the following pseudocode:

initialize iterator with nestedList res = [] while iterator.hasNext() append iterator.next() to the end of res return res If res matches the expected flattened list, then your code will be judged as correct.

Example 1: Input: nestedList = [[1,1],2,[1,1]] Output: [1,1,2,1,1] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2: Input: nestedList = [1,[4,[6]]] Output: [1,4,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Constraints:

1 <= nestedList.length <= 500 The values of the integers in the nested list is in the range [-10^6, 10^6].

Python
# Two stacks
# time - Constructor: O(1), makeStackTopAnInteger() / next() / hasNext(): O(L/N) or O(1); space = O(D)
# where N = # integers in nested list, L = total # lists in nested list, and D = max nesting depth 
class NestedIterator:
    
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = [[nestedList, 0]]
        
    def make_stack_top_an_integer(self):
        
        while self.stack:
            
            # Essential for readability :)
            current_list = self.stack[-1][0]
            current_index = self.stack[-1][1]
            
            # If the top list is used up, pop it and its index.
            if len(current_list) == current_index:
                self.stack.pop()
                continue
            
            # Otherwise, if it's already an integer, we don't need 
            # to do anything.
            if current_list[current_index].isInteger():
                break
            
            # Otherwise, it must be a list. We need to increment the index
            # on the previous list, and add the new list.
            new_list = current_list[current_index].getList()
            self.stack[-1][1] += 1 # Increment old.
            self.stack.append([new_list, 0])
            
    
    def next(self) -> int:
        self.make_stack_top_an_integer()
        current_list = self.stack[-1][0]
        current_index = self.stack[-1][1]
        self.stack[-1][1] += 1
        return current_list[current_index].getInteger()
        
    
    def hasNext(self) -> bool:
        self.make_stack_top_an_integer()
        return len(self.stack) > 0
Python
# Using generators
# time - Constructor: O(1), next() / hasNext(): O(L/N) or O(1); space = O(D)
class NestedIterator:

    def __init__(self, nestedList: [NestedInteger]):
        # Get a generator object from the generator function, passing in
        # nestedList as the parameter.
        self._generator = self._int_generator(nestedList)
        # All values are placed here before being returned.
        self._peeked = None

    # This is the generator function. It can be used to create generator
    # objects.
    def _int_generator(self, nested_list) -> "Generator[int]":
        # This code is the same as Approach 1. It's a recursive DFS.
        for nested in nested_list:
            if nested.isInteger():
                yield nested.getInteger()
            else:
                # We always use "yield from" on recursive generator calls.
                yield from self._int_generator(nested.getList())
        # Will automatically raise a StopIteration.
    
    def next(self) -> int:
        # Check there are integers left, and if so, then this will
        # also put one into self._peeked.
        if not self.hasNext(): return None
        # Return the value of self._peeked, also clearing it.
        next_integer, self._peeked = self._peeked, None
        return next_integer
        
    def hasNext(self) -> bool:
        if self._peeked is not None: return True
        try: # Get another integer out of the generator.
            self._peeked = next(self._generator)
            return True
        except: # The generator is finished so raised StopIteration.
            return False

Other

Here are some other questions for you to practice for your Apple interview. These are usually related to Math problems. We also added a database question (Combine Two Tables) which may be applicable, depending on the position you're applying for

7. Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123 Output: 321 Example 2:

Input: x = -123 Output: -321 Example 3:

Input: x = 120 Output: 21

Constraints:

-231 <= x <= 231 - 1

Algorithm

Reversing an integer can be done similarly to reversing a string.

We want to repeatedly "pop" the last digit off of xx and "push" it to the back of the \text{rev}rev. In the end, \text{rev}rev will be the reverse of the x. To "pop" and "push" digits without the help of some auxiliary stack/array, we can use math.

//pop operation: pop = x % 10; x /= 10;

//push operation: temp = rev * 10 + pop; rev = temp;

However, this approach is dangerous, because the statement temp=rev⋅10+pop can cause overflow. Luckily, it is easy to check beforehand whether or this statement would cause an overflow

Python
# time = O(log(x)) - roughly log10(x) digits in x; space = O(1)
# Java
class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

771. Jewels and Stones

You're given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1: Input: jewels = "aA", stones = "aAAbbbb" Output: 3

Example 2: Input: jewels = "z", stones = "ZZ" Output: 0

Constraints:

1 <= jewels.length, stones.length <= 50 jewels and stones consist of only English letters. All the characters of jewels are unique

Python
# time = O(J.length∗S.length)), space O(1) in Python
# For each stone, check whether it matches any of the jewels. We can check with a linear scan
class Solution(object):
    def numJewelsInStones(self, J, S):
        return sum(s in J for s in S)
Python
# time = O(J.length∗S.length)), space O(J.length)
# For each stone, check whether it matches any of the jewels. We can check efficiently with a Hash Set
class Solution(object):
    def numJewelsInStones(self, J, S):
        Jset = set(J)
        return sum(s in Jset for s in S)

36. Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules.

Example 1: 

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

Output: true Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

board.length == 9 board[i].length == 9 board[i][j] is a digit 1-9 or '.'.

Bit masking algo

Python
# Bit masking
# time = O(N^2), space = O(N)
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        N = 9
        # Use binary number to check previous occurrence
        rows = [0] * N
        cols = [0] * N
        boxes = [0] * N

        for r in range(N):
            for c in range(N):
                # Check if the position is filled with number
                if board[r][c] == ".":
                    continue

                pos = int(board[r][c]) - 1

                # Check the row
                if rows[r] & (1 << pos):
                    return False
                rows[r] |= (1 << pos)

                # Check the column
                if cols[c] & (1 << pos):
                    return False
                cols[c] |= (1 << pos)

                # Check the box
                idx = (r // 3) * 3 + c // 3
                if boxes[idx] & (1 << pos):
                    return False
                boxes[idx] |= (1 << pos)

        return True
Python
# Hash set
# time = O(N^2), space = O(N^2)
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        N = 9

        # Use hash set to record the status
        rows = [set() for _ in range(N)]
        cols = [set() for _ in range(N)]
        boxes = [set() for _ in range(N)]

        for r in range(N):
            for c in range(N):
                val = board[r][c]
                # Check if the position is filled with number
                if val == ".":
                    continue

                # Check the row
                if val in rows[r]:
                    return False
                rows[r].add(val)

                # Check the column
                if val in cols[c]:
                    return False
                cols[c].add(val)

                # Check the box
                idx = (r // 3) * 3 + c // 3
                if val in boxes[idx]:
                    return False
                boxes[idx].add(val)

        return True
Python
# Array of fixed length
# time = O(N^2), space = O(N^2)
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        N = 9

        # Use an array to record the status
        rows = [[0] * N for _ in range(N)]
        cols = [[0] * N for _ in range(N)]
        boxes = [[0] * N for _ in range(N)]

        for r in range(N):
            for c in range(N):
                # Check if the position is filled with number
                if board[r][c] == ".":
                    continue

                pos = int(board[r][c]) - 1

                # Check the row
                if rows[r][pos] == 1:
                    return False
                rows[r][pos] = 1

                # Check the column
                if cols[c][pos] == 1:
                    return False
                cols[c][pos] = 1

                # Check the box
                idx = (r // 3) * 3 + c // 3
                if boxes[idx][pos] == 1:
                    return False
                boxes[idx][pos] = 1

        return True

175. Combine Two Tables

Table: Person

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| personId    | int     |
| lastName    | varchar |
| firstName   | varchar |
+-------------+---------+

personId is the primary key column for this table. This table contains information about the ID of some persons and their first and last names.

Table: Address

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| addressId   | int     |
| personId    | int     |
| city        | varchar |
| state       | varchar |
+-------------+---------+

addressId is the primary key column for this table. Each row of this table contains information about the city and state of one person with ID = PersonId.

Write an SQL query to report the first name, last name, city, and state of each person in the Person table. If the address of a personId is not present in the Address table, report null instead.

Return the result table in any order.

The query result format is in the following example.

Example 1:

Input: Person table:

+----------+----------+-----------+
| personId | lastName | firstName |
+----------+----------+-----------+
| 1        | Wang     | Allen     |
| 2        | Alice    | Bob       |
+----------+----------+-----------+
Address table:
+-----------+----------+---------------+------------+
| addressId | personId | city          | state      |
+-----------+----------+---------------+------------+
| 1         | 2        | New York City | New York   |
| 2         | 3        | Leetcode      | California |
+-----------+----------+---------------+------------+
Output: 
+-----------+----------+---------------+----------+
| firstName | lastName | city          | state    |
+-----------+----------+---------------+----------+
| Allen     | Wang     | Null          | Null     |
| Bob       | Alice    | New York City | New York |
+-----------+----------+---------------+----------+

Explanation: There is no address in the address table for the personId = 1 so we return null in their city and state. addressId = 1 contains information about the address of personId = 2.

Python
select FirstName, LastName, City, State
from Person left join Address
on Person.PersonId = Address.PersonId

178. Rank Scores

Table: Scores

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| score       | decimal |
+-------------+---------+

id is the primary key for this table. Each row of this table contains the score of a game. Score is a floating point value with two decimal places.

Write an SQL query to rank the scores. The ranking should be calculated according to the following rules:

The scores should be ranked from the highest to the lowest. If there is a tie between two scores, both should have the same ranking. After a tie, the next ranking number should be the next consecutive integer value. In other words, there should be no holes between ranks. Return the result table ordered by score in descending order.

The query result format is in the following example.

Example 1:

Input: Scores table:

+----+-------+
| id | score |
+----+-------+
| 1  | 3.50  |
| 2  | 3.65  |
| 3  | 4.00  |
| 4  | 3.85  |
| 5  | 4.00  |
| 6  | 3.65  |
+----+-------+
Output: 
+-------+------+
| score | rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+
Python
# MySQL (preferred approach)
SELECT
  S1.score,
  (
    SELECT
      COUNT(DISTINCT S2.score)
    FROM
      Scores S2
    WHERE
      S2.score >= S1.score
  ) AS 'rank'
FROM
  Scores S1
ORDER BY
  S1.score DESC;
Python
# MySQL
SELECT
  S.score,
  COUNT(DISTINCT T.score) AS 'rank'
FROM
  Scores S
  INNER JOIN Scores T ON S.score <= T.score
GROUP BY
  S.id,
  S.score
ORDER BY
  S.score DESC;

202. Happy Number

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.

Example 1:
Input: n = 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Example 2:
Input: n = 2
Output: false

Constraints:

1 <= n <= 2^31 - 1

Python
# Detect Cycles with a HashSet
# time = O(243⋅3+logn+loglogn+logloglogn)... = O(logn); space = O(logn)
def isHappy(self, n: int) -> bool:

    def get_next(n):
        total_sum = 0
        while n > 0:
            n, digit = divmod(n, 10)
            total_sum += digit ** 2
        return total_sum

    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = get_next(n)

    return n == 1
Python
# Floyd's Cycle-Finding Algorithm
# time = O(logn); space = O(1)
def isHappy(self, n: int) -> bool:  
    def get_next(number):
        total_sum = 0
        while number > 0:
            number, digit = divmod(number, 10)
            total_sum += digit ** 2
        return total_sum

    slow_runner = n
    fast_runner = get_next(n)
    while fast_runner != 1 and slow_runner != fast_runner:
        slow_runner = get_next(slow_runner)
        fast_runner = get_next(get_next(fast_runner))
    return fast_runner == 1
Python
# Hardcoding the Only Cycle (Advanced)
# time = O(logn); space = O(1)
'''
The previous two approaches are the ones you'd be expected to come up with in an interview.
This third approach is not something you'd write in an interview, but is aimed at the mathematically curious
among you as it's quite interesting.

What's the biggest number that could have a next value bigger than itself?
Well we know it has to be less than 243, from the analysis we did previously. Therefore, we know that 
any cycles must contain numbers smaller than 243, as anything bigger could not be cycled back to. 
With such small numbers, it's not difficult to write a brute force program that finds all the cycles.

If you do this, you'll find there's only one cycle: 4 => 16 => 37 => 58 => 89 => 145 => 42 => 20 => 4.
All other numbers are on chains that lead into this cycle, or on chains that lead into 1.

Therefore, we can just hardcode a HashSet containing these numbers, and if we ever reach one of them,
then we know we're in the cycle. There's no need to keep track of where we've been previously.
'''
def isHappy(self, n: int) -> bool:

    cycle_members = {4, 16, 37, 58, 89, 145, 42, 20}

    def get_next(number):
        total_sum = 0
        while number > 0:
            number, digit = divmod(number, 10)
            total_sum += digit ** 2
        return total_sum

    while n != 1 and n not in cycle_members:
        n = get_next(n)

    return n == 1

412. Fizz Buzz

Given an integer n, return a string array answer (1-indexed) where:

answer[i] == "FizzBuzz" if i is divisible by 3 and 5. answer[i] == "Fizz" if i is divisible by 3. answer[i] == "Buzz" if i is divisible by 5. answer[i] == i (as a string) if none of the above conditions are true.

Example 1: Input: n = 3 Output: ["1","2","Fizz"]

Example 2: Input: n = 5 Output: ["1","2","Fizz","4","Buzz"]

Example 3: Input: n = 15 Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

Constraints:

1 <= n <= 10^4

Python
# Naive
# time = O(N), space = O(1)
class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        # ans list
        ans = []

        for num in range(1,n+1):

            divisible_by_3 = (num % 3 == 0)
            divisible_by_5 = (num % 5 == 0)

            if divisible_by_3 and divisible_by_5:
                # Divides by both 3 and 5, add FizzBuzz
                ans.append("FizzBuzz")
            elif divisible_by_3:
                # Divides by 3, add Fizz
                ans.append("Fizz")
            elif divisible_by_5:
                # Divides by 5, add Buzz
                ans.append("Buzz")
            else:
                # Not divisible by 3 or 5, add the number
                ans.append(str(num))

        return ans
Python
# str concat
# time = O(N), space = O(1)
class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        # ans list
        ans = []

        for num in range(1,n+1):

            divisible_by_3 = (num % 3 == 0)
            divisible_by_5 = (num % 5 == 0)

            num_ans_str = ""

            if divisible_by_3:
                # Divides by 3
                num_ans_str += "Fizz"
            if divisible_by_5:
                # Divides by 5
                num_ans_str += "Buzz"
            if not num_ans_str:
                # Not divisible by 3 or 5
                num_ans_str = str(num)

            # Append the current answer str to the ans list
            ans.append(num_ans_str)  

        return ans
Python
# hashing
# time = O(N), space = O(1)
class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        # ans list
        ans = []

        # Dictionary to store all fizzbuzz mappings
        fizz_buzz_dict = {3 : "Fizz", 5 : "Buzz"}
        
        # List of divisors which we will iterate over.
        divisors = [3, 5]

        for num in range(1, n + 1):

            num_ans_str = []

            for key in divisors:
                # If the num is divisible by key,
                # then add the corresponding string mapping to current num_ans_str
                if num % key == 0:
                    num_ans_str.append(fizz_buzz_dict[key])

            if not num_ans_str:
                num_ans_str.append(str(num))

            # Append the current answer str to the ans list
            ans.append(''.join(num_ans_str))

        return ans