Arrays & Strings

Question 1

Two Sum (Easy)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Answer 1

Create map of nums to index
iterate through array and look for complement in map

Time - O(n)
Space - O(n)

Question 2

First Missing Positive (Hard)

Given an unsorted integer array, find the smallest missing positive integer.

Answer 2

Check for 1 - if not found return 1
If 1 found but array length 1, return 2
Sanitize array of negatives and numbers greater than array length (first missing positive guaranteed to be less than array length) - set values to 1 since its already found
Use index as hash key and sign to indicate presence - negative means number there, positive means missing. Use Math.abs() to avoid double sign flipping
Use index 0 to track n (array length)
First index of missing positive is answer
If not found, check 0 for n (array length)
If not found, return n + 1

Time - O(n)
Space - O(1)

Question 3

Group Anagrams (Medium)

Given an array of strings, group anagrams together.

Answer 3

Create map of string key to array of strings with that key
Iterate through array
For each string, create a key that will be the same for anagrams (split/sort/join) and set value to array
Push string to matching array

Time - O(n)
Space - O(n)

Question 4

Maximum Subarray (Easy)

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

Answer 4

Kadane's Algorithm
Initialize currSum and maxSum as nums[0]
Iterate
currSum = Math.max(currSum, currSum + nums[i])
maxSum = Math.max(currSum, maxSum)

Time - O(n)
Space - O(1)

Question 5

Rotate Array (Easy)

Given an array, rotate the array to the right by k steps, where k is non-negative.

Answer 5

Modulo k by array length
Reverse array
Reverse first k
Reverse last n - k

Time - O(n)
Space - O(1)

Question 6

Product of Array Except Self (Medium)

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Answer 6

Iterate forwards and compute cumulative left product
ans[0] = 1
ans[i] = nums[i - 1] * ans[i - 1]
Iterate backwards, keep running product
product = 1, product *= nums[j + 1]
ans[i] *= product

Time - O(n)
Space - O(1)

Question 7

Group Shifted Strings (Medium)

Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:
“abc” -> “bcd” -> … -> “xyz”
Given a list of non-empty strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

Answer 7

Create map for string key to array of strings
Hash each string by looking at char code difference w/ previous character
If difference is negative, add 26 to roll it back around
Join with ‘#’

Time - O(n * string length)
Space - O(n)

Question 8

Continuous Subarray Sum (Medium)

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.

Answer 8

Create map of sum remainders and index
Set map(0, -1)
Cumulate sum and get remainder (sum += nums[i], sum %= k)
If map has remainder, calc difference between i and map.get(sum), if > 1, found
Set remainder in map (map.set(sum, i))

Time - O(n)
Space - O(n)

Question 9

Subarray Sum Equals K (Medium)

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Answer 9

Track cumulative sum and count
Create map of sums to num occurrences of those sums
Set map(0, 1)
sum += nums[i]
if (map.has(sum - k) count += map.get(sum - k)
map.set(sum, map.get(sum) + 1)

Time - O(n)
Space - O(n)

Question 10

Search In a Sorted Array of Unknown Size (Medium)

Given an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return -1. However, the array size is unknown to you. You may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0-indexed).

Answer 10

First, find range
Start = 0, End = 1
While reader.get(End) < target, start = end, end «= 1
Binary search w/in start/end

Time - O(log T) where T is target index
Space - O(1)

Question 11

Buddy Strings (Medium)

Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.

Answer 11

Strings need to be equal length
If strings equal, need to be at least 2 matching chars to swap. Iterate through tracking char counts to verify at least one char occurs twice
If strings not equal, track index of first mismatch and second mismatch while iterating
If third mismatch encountered = false
Verify A[first] = B[second] & A[second] = B[first]

Time - O(n)
Space - O(n) (if equal strings), O(1) otherwise

Question 12

Verifying An Alien Dictionary (Easy)

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Answer 12

Build priority dictionary
map.set(order[i], i)
Iterate through words, checking 2 at a time
If end of list, in order!
Find first character difference
If first character difference is that next word is shorter, not in order!
Check priorities of first difference to verify proper order, then continue

Time - O(order.length + words.length * word.length)
Space - O(order.length)

Question 13

Missing Element in Sorted Array (Medium)

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

Answer 13

Missing = nums[idx] - nums[0] - idx
If k > missing(n - 1), return nums[n - 1] + k - missing(n - 1)
Binary search
if (missing(mid) < k) left = mid + 1
else right = mid
return nums[left - 1] + k - missing(left - 1)

Time - O(log n)
Space - O(1)

Question 14

Median of Two Sorted Arrays (Hard)

Given two sorted arrays nums1 and nums2 of size m and n respectively.

Return the median of the two sorted arrays.

Answer 14

Make sure A is shortest array
halfLength = (A.length + B.length + 1) / 2
Binary search through probability space iMin = 0, iMax = A.length
i = iMin + floor((iMax - iMin) / 2)
j = halfLength - i
if i < iMax & B[j - 1] > A[i] iMin = i + 1
if i > iMin & A[i - 1] > B[j] iMax = i - 1
else
calc maxLeft - if i = 0, maxLeft = B[j - 1], if j = 0, maxLeft = A[i - 1], else maxLeft = max(A[i - 1], B[j - 1])
if (A.length + B.length is odd) return maxLeft
calc minRight - if i = A.length, minRight = B[j], if j = B.length minRight = A[i], else min(A[i], B[j])
return maxLeft + minRight / 2

Time - O(log min(A.length, B.length))
Space - O(1)