TwoSum
This is a classic introductory problem & it is a good place for us to start our leetcode journey. Read over the problem statement below.
Pretty straightforward right? Let's take this step by step and make sure we understand the solution. We need the indices of 2 numbers that add up to a target. We can assume there is one answer, and we may not use the same element twice. Easy enough.
Brute Force
A brute force solution here is pretty obvious, let's go through each element in the array, and iterate over every other element, to see if we add up to a target. This is a common brute force method for most array problems. This will give us a O(n²) time & O(1) spacial solution. Let's write some pseudocode for this solution and test it. While testing, make sure to capture edge cases!
for number in array
for every other number in array
if number + other number = target
return [number index, other number index]
It is time to consider some bottlenecks, and think how we can optimize our solution. Firstly, if you notice some nested for loops in your code, that is a code smell. Think how those can be optimized. In our case if we try to pass thru the array only once, while also sequentially finding the solution, we heavily optimize our solution.
Approach 1
[ Sort + 2 pointer ]
[ O(nLog(n)) time + O(n) space ]
For this specific problem we know we want 2 numbers that add up to a target. That is, X + Y = Z. If we have X, we know that we are searching for Z - Y. If we sort our array, we can make this search much faster.
Back to our above example, we have an array of [4, 2, 1, 3] and we need a target of 3. If we first sort the array, we can use 2 pointers to incrementally get closer to our target number. By sorting our array is [1, 2, 3, 4]. We have a left pointer at the beginning of the array and a right pointer at the end of the array. Let's add these numbers up. 1 + 4 = 5, which is greater than our target of 3. The sum is greater than our target, so let's move the right pointer inward. Now our pointers are targeted at 1, and 3. 1 + 3 = 4, a summation that is still greater than our target. So we move the right pointer inward once more. This makes our pointers at 1 and 2, and if we add those up we find our target.
Pseudocode:
sort array
while left pointer < right pointer
add up left and right pointers
if sum = target
return left and right pointer
if sum > target
move right pointer
if sum < target
move left pointer
There are some considerations here. By sorting we can get, on average, O(nLog(n)) time performance. So by sorting and then searching our array we are looking at O(nLog(n)) + O(n) time complexity. Which comes out to be O(nLog(n)). This is a pretty significant time vs space tradeoff and this should be discussed with your interviewer.
Let's go into implementation now.
// edge case for empty array + single element in array.
guard nums.count > 1 else { return [Int]() }
let sorted = nums.sorted()
var leftPointer = 0
var rightPointer = nums.count - 1
// Search our array
while leftPointer < rightPointer {
let sum = sorted[leftPointer] + sorted[rightPointer]
if sum > target {
rightPointer -= 1
} else if sum < target {
leftPointer += 1
} else {
break
}
}
// Because the swift index(of:) function returns us an 'Array<Int>.Index?'
// we need to manually get the integer Index value by doing one more loop.
let leftNum = sorted[leftPointer]
let rightNum = sorted[rightPointer]
var returnValue = [Int]()
// Beautiful swift! Reads just like english :)
for (i, num) in nums.enumerated() where (num == leftNum || num == rightNum) {
returnValue.append(i)
}
return returnValue
Ta-Da! This is one passing solution to solve the 2 sum problem. This methodology will be the preferred method of solving in 3sum, 4sum and etc problems.
Approach 2
[ Hash Table ]
[ O(n) time + space ]
By using some auxiliary data structure for storage you can easily look up past calculations for your use case. In our case, we should try to optimize our O(n²) time solution into a O(n) time solution. For array problems this is the mecca. This brings us to our introduction of hash tables/dictionary's. We can have constant lookup in swift dictionaries.
In our case let's consider we loop through the array 1 time, and in a hash table, we store the key as the element of our array and the value as the index of each value. So our original array of [4, 2, 1, 3] turns into a dictionary of [4: 0, 2: 1, 1: 2, 3: 3]. Now in our problem, we can go through our array 1 time, and at each element we can see if the inverse of the target exists. Namely it comes down to this pseudocode:
for number in array
add to dictionary. [number: index of number]
for number in array
inverse = target - number
if dictionary[inverse] exists
return [number, dictionary[inverse]]
After testing, we see this is a lot more efficient, and it works! We gave up some constant space in order for time efficiency, but these tradeoffs are things you can discuss with your interviewer. Now let's code our final solution. Don't forget to cover those edge cases, and to practice safe optional unwrapping!
// edge case for empty array + single element in array.
guard nums.count > 1 else { return [] }
var hashTable = [Int:Int]()
// Create our hashtable mapping
for (index, element) in nums.enumerated() {
hashTable[element] = index
}
// Now search our array for the inverse!
for (index, element) in nums.enumerated() {
let inverse = target - element
// we should not be using the same element within itself. Make sure to read the problem carefully!
if let existingInverse = hashTable[inverse], unwrappedInverse != index {
return [existingInverse, index]
}
}
return [] // we have no solution.
Nice work!
ThreeSum
This problem builds off of our previous problem, with a little more complexity. Check out the problem statement below.
If we remember one of the solutions for the TwoSum problem, when we sort the array then use 2 pointers to find our target it leads to decently efficient code.
Brute Force
With most array problems, the brute force solution is straightforward. By using nested loops, we can iterate on all possible answer combinations until we find the solution(s) we want. In this case, this is an O(n³) solution. With all of our "sum" problems we can represent the brute force as a O(nˣ) where x = the number 'sum' the problem is asking for.
Pseudocode:
for number in array
for secondNumber in array
for thirdNumber in array
if number + secondNumber + thirdNumber = 0 AND we have not added this answer combination before
add these numbers to our return value
Obviously the nested nature of these arrays should be avoided. So let's take a step back and iterate on our approach from the TwoSum problem.
Approach
[ Sort + 2 pointer ]
[ O(n²) time + O(n) space ]
We know we need to add up to a target of 0, with 3 different numbers. In formulaic terms, we have X + Y + Z = 0. For each element in our array, we have one of the elements in our equation. So we are left with -Z = X + Y, where Z is our element in the array.
By sorting our array at the beginning of our function, we can reuse our TwoSum logic. Add up X + Y. If that sum is less than our target (-Z) we need to increase our sum & vice versa. Since our array is sorted, and we can represent X and Y as leftPointer's and rightPointer's in our array, it is easy to increase and decrease our sum as needed. Namely we can do something similar to this.
sort array
for number in sorted array
find the targetNumber
find the leftPointer
find the rightPointer
while leftPointer less than rightPointer
sum = leftPointer + rightPointer
if sum is less than target
move leftPointer inward
if sum is greater than target
move rightPointer inward
if sum equals target AND not duplicated
we have our combination!
add to answer
move both leftPointer and rightPointer inward
Some time + space considerations here. By sorting we have O(nLog(n)) and then searching every element in the array gives us O(nLog(n)) + O(n²). Since O(n²) is much greater than O(nLog(n)), the O(nLog(n)) cancels out and does not need to be considered in the final time complexity calculations, so the final time complexity is O(n²) time where n is the length of our input array. For space, we need to keep track of the answer in an array, so the space complexity is O(n) where n is the length of the answer.
Let's implement the real answer.
// edge case for empty array + single element + only 2 elements in array.
guard nums.count > 2 else { return [[Int]]() }
var returnVal = [[Int]]()
let sorted = nums.sorted()
for (index, element) in sorted.enumerated() {
let target = 0 - element
var leftPointer = index + 1
var rightPointer = sorted.count - 1
// search for our target, within bounds
while leftPointer < rightPointer {
let sum = sorted[leftPointer] + sorted[rightPointer]
if sum < target {
leftPointer += 1 // Sum is too small, increase our sum
} else if sum > target {
rightPointer -= 1 // Sum is too big, decrease our sum
} else if sum == target {
// We found an answer!
let correctAns = [element, sorted[leftPointer], sorted[rightPointer]]
// Preemptively move our pointers inward
leftPointer += 1
rightPointer -= 1
if !(returnVal.contains(correctAns)) {
// add to our answer
returnVal.append(correctAns)
}
}
}
}
return returnVal
Boom! Nicely done.
Contains Duplicates
This is a pretty straightforward problem, but builds our foundational knowledge when it comes to HashTables! Find the problem statement below.
Very easy problem to grasp. Now let's try to find ourselves a brute force solution, and optimize it.
Brute Force
A very easy brute force solution, leads us to an O(n²) time complexity solution with O(1) space. This would be to go by each element in the array, and have a nested loop to see if our outer element is found within our inner loop. Like so:
for number in array
for every other number in array
if number equals other number we have found a duplicate.
By introducing a HashTable into the problem, we know that HashTable's have constant lookup, but at worst, they take up O(n) space where N = length of the input array. Also since HashTable's have unique keys, we will be able to store all of the elements in our array just once.
Approach
[ HashTable + Consistent Lookup ]
[ O(n) time + O(n) space ]
We can initialize a HashTable at the beginning of our problem, where the key of the HashTable is the same type of element in our input array, in this case Integer. As we loop through our array, we can check if the HashTable already contains a key-element pair that matches Integer at each iteration of the loop. If the key-element pair exists, we can break out of the loop, and return true for our function. If the key-element pair does not exist, we can add it to the HashTable.
Create HashTable with key of Integer and element of whatever you would like
for number in array
if element exists with number as the key
return true
else
add to the HashTable
Pretty simple right! Like I mentioned above, the time and space are both O(n). This is why HashTables are so powerful, is because they give us consistent lookup time when we need some auxiliary storage in our problems. Now it is time to implement the real solution.
guard nums.count > 1 else { return false } // edge-case check against small or empty inputs
var hashTable = [Int:Int]() // i opted for an Int:Int pair, but you could have easily done Int:Bool, etc.
for (index, element) in nums.enumerated() { // loop our input array
if hashTable[element] != nil {
return true // We have found a duplicate!
} else {
hashTable[element] = index // Add element to HashTable
}
}
return false // No duplicates here...
Easy-Peasy.
Product Of Array Except Self
This problem is our first introduction on how to traverse an array both forwards and backwards! Let's dive in.
We need to come up with a brute force solution to start, and like every other array problem, we can nest iterations in order to get every possible combination in the array.
Brute Force
We can start at each point in a given array and calculate every other arrays product, and add it to a return value. This leads us to a O(n²) time complexity and an O(n) spatial complexity because we need to store the length of the return array in our function. This is O(n²) time due to the nested nature of our iterations within the array.
for number in array
iterate through rest of array
calculate the product
add product to return value
Approach
[ Forward + Backward Iteration ]
[ O(n) time + O(n) space ]
We can optimize this problem by filling in our return array only twice. We can loop forward through our auxiliary return array once, keep a running product at each iteration, and use the running product to fill our return value array. Then we can reset our running product count, and iterate our array backwards to keep a running count of all the values minus itself.
The thinking here is, as we iterate our array we can fill in our return value in place. On the first loop, returnArray[i] will contain proceeding product of nums[i] (exclusive). After the second loop, each returnArray[i] is updated by multiplying to succeeding product of nums[i].
keep running count starting at 1
create return array of all 1's
for number in array forward direction
update return array with running count
update running count by multiplying number to existing count
reset running count
for number in array backwards direction
update return array by multiplying running count by number in input array
update running count by multiplying number to existing count
return
This gives us an O(n) time solution since we only have to iterate twice, namely forward and backwards. O(2n) = O(n) on average. Space is still consistently O(n). Now let's implement the real solution.
guard nums.count > 0 else { return [] } // guard against edge cases
var auxArray = Array(repeating: 1, count: nums.count) // create a return array of all 1's
var runningCount = 1
for index in 0..<nums.count { // forward iteration
auxArray[index] = runningCount
runningCount *= nums[index] // update running count of product
}
runningCount = 1 // reset the running count
for index in stride(from: nums.count - 1, through: 0, by: -1) { // backward iteration
auxArray[index] *= runningCount
runningCount *= nums[index] // update running count of product
}
return auxArray
Good Job!
Valid Anagram
This problem expands our knowledge on array best practices! Let's tackle it.
Brute Force
Let's start by thinking of a brute force solution. My brute force solution I came up with involved a little different of an approach as opposed to other array problems. Nesting arrays in this problem isn't quite where my head first went. Initially I thought it would be easiest to sort both input strings, and then go letter by letter to compare the two strings. When we find a deviation between the two, we do not have a valid anagram.
sort string s
sort string t
make sure they are the same length
for letter in s or t length
if letter in s does not equal letter in t
return false
if we get here, we have a valid anagram
Looping the strings is not the issue here. Sorting 2 different strings, and then looping is not very optimal. By sorting we can get, on average, O(nLog(n)) time performance. Make that sorting twice plus looping the strings we are looking at O(2nLog(n)) + O(n) time complexity. We can simplify this to O(3nLog(n)) -> O(nLog(n)) time, with O(1) consistent space complexity.
We know we can do better though. It may be worth giving up our consistent space complexity to get a better time complexity.
Approach
[ HashTable with letter occurrences ]
[ O(n) time + O(n) space ]
We can introduce our arrays best friend! A hash table. We can store the occurrences of each letter in our hashTable. Utilizing a hash table here gives us consistent O(1) lookup when we need to know how many times we have seen a character. We have 2 strings, for one string we can increase the number of occurrences, for another string we can decrease the number of occurrences. In a perfect world, our hash table should have values of all 0's if it is a valid anagram.
check string lengths are equal
create hash table
for letter in s
if our hash table contains this letter already
increment its occurrence number by 1
if our hash table does not contain this letter
add it to the hash table with an occurrence of 1
for letter in t
if our hash table contains this letter already
decrement its occurrence number by 1
if our hash table does not contain this letter
return false; we have found a letter in t that s does not have
for values in our hash table
if our value is not 0
return false
return true
This solution contains 3 loops. This equates to O(3n) → O(n) on average time complexity. Our space complexity is O(n) where n is the number of unique characters in s and t. This can also be represented as O(max(s.length, t.length)) at worst case. It's time to bring it all together:
guard s.count == t.count else { return false } // edge case where our string lengths may not be equal
var hashTable = [Character:Int]()
for letter in s {
if let existing = hashTable[letter] {
hashTable[letter] = existing + 1 // if we have already seen this character, append its count by 1
} else {
hashTable[letter] = 1 // we have not seen this character yet, add to hash table
}
}
for letter in t {
if let existing = hashTable[letter] {
hashTable[letter] = existing - 1 // decrement the character occurrence by 1
} else {
return false // t contains a letter s does not have. not a valid anagram
}
}
for item in hashTable.values {
if item != 0 { return false } // we have found a letter where s contains more occurrences than t, and vice versa
}
return true // valid!
Nice!
Valid Palindrome
Similar to our problem with Anagrams, this problem is a play on a string, but can easily be thought of as an array problem. One thing to note about this problem is PAY ATTENTION! The little details on some of these leetcode problems can kill you. Notice we should ignore non alphanumeric characters + ignore spaces. Also notice how we should be treating all alphanumerics as lowercased.
Brute Force
As always we start with a Brute Force solution and optimize. Here we can think of the string as an array of characters. Initially we can consider the option of nested arrays with a pointer. We start at the first letter, traverse to the last letter, and make sure they match. Then go to the 2nd letter, traverse to the 2nd to last letter and see if they match. We can do this for all letters nums[x]...nums[length-x] until we meet in the middle.
for alphanumeric character in string
traverse to length - x letter of the string, that is alphanumeric
if letters are the same
continue
else
return false
The bottleneck within this problem is the inner traversal of the string to get to the length - x character in the string. Our brute force solution is on average O(n²) time complexity, with a consistent O(1) spatial complexity. We do not keep any extra storage so we do not take up any extra space. Depending how we check if numbers are alphanumeric, our time complexity may be even slower than O(n²).
Approach
[ 2 pointers ]
[ O(n) time + O(1) space ]
We can utilize the 2 pointer method, commonly found in arrays for this problem. If we take our string, and put a pointer at the beginning and end of the string, we can move our 2 pointers closer together until they meet in the middle, with O(1/2n) time complexity -> which averages out to O(n).
We should also take considerations on how to check if a character is alphanumeric. We could create an array of letters and an array of numbers, and check if those array's contain our character. By doing this we introduce poor time complexity into our code. Say our string contains multiple Z's. We would need to traverse the entire alphabet array to see if the character is a letter. A more efficient solution would be to utilize properties on the Swift Standard Library. The Character object comes with built in "isLetter" and "isNumber" properties. Under the hood Swift compares the ASCII encoding value of your character to different ranges of letters and numbers, to ensure it is alphanumeric. This is a much more efficient solution than the array of letters approach.
create left pointer
create right pointer
create array of lowercased letters // O(n)
while left pointer <= right pointer // O(1/2n) at worst
make sure left pointer is alphanumeric
if not, continue thru the loop
make sure right pointer is alphanumeric
if not, continue thru the loop
if left pointer does not equal right pointer
return false
move left and right pointers inward in the array
We do not necessarily have to convert our string into an array of lowercased letters. I chose to do this because of the difficulty of indexing a string in swift. To index a certain letter in a string, you cannot just subscript like: str[9]. You must use the built in String.Index type. So for proper, clean code you may implement something like this:
extension StringProtocol {
subscript(offset: Int) -> Character {
self[index(startIndex, offsetBy: offset)]
}
}
Given the short amount of time in a leetcode interview, I tend to stay away, and just convert to an array when possible. Make sure to weigh trade-offs with your interviewer though! If keep the structure as the original string, we would just have to convert the letters to lowercase on each comparison.
Let's implement our O(n) time, and O(1) space solution.
guard s.count > 1 else { return true } // guard against edge cases
var leftPointer = 0, rightPointer = s.count - 1 // create our pointers
var arr = Array(s.lowercased()) // convert to an array
while leftPointer <= rightPointer { // loop until our pointers meet in the middle
guard arr[leftPointer].isLetter || arr[leftPointer].isNumber else { // make sure left is alphanumeric
leftPointer += 1 // if not, move left pointer inward and continue the loop
continue
}
guard arr[rightPointer].isLetter || arr[rightPointer].isNumber else { // make sure right is alphanumeric
rightPointer -= 1 // if not, move the right pointer inward and continue the loop
continue
}
if arr[leftPointer] != arr[rightPointer] { // if our letters are not equal, return false
return false
}
leftPointer += 1 // move left inward
rightPointer -= 1 // move right inward
}
return true
Great Job! and remember, keep an eye out for the little details in a problem description.
Group Anagrams
This next problem expands our previous knowledge around what makes an anagram valid. Now let's use this base knowledge to group similar sets of anagrams!
Brute Force
The brute force solution for this problem is pretty straight forward. We can use nested For Loops to find all the anagram groups for a given element, group similar ones, and return the groups in a nested return array.
for word in array
start an anagram group array
for every other word in the array
if outer and inner word are valid anagrams of each other & not in anagram group array
add words to anagram group array
add anagram group array to return value
return the return value
This is obviously an inefficient solution due to the 2 nested arrays. This solution would give us an O(n²) time solution + the time to check if the words are anagrams of one another + the time to check if the words are not in an anagram array. This total time equates to O(n²xw), where n is the length of the input array, x is the length of the longest word, and w is the length of the longest anagram array. Not great. Space complexity is O(n) where n is the length of the return value.
Approach
[ Sort + HashTable ]
[ O(wnLog(n)) time + O(wn) space ]
The bottle necks we can identify from our brute force solution, is obviously: validating 2 words are anagrams of one another, and the grouping mechanism of the nested loops. We need to be able to find the groups faster.
One easy way to think about this is: We can find if two strings are anagrams of one another by sorting the letters in the strings alphabetically. For example, we know "rat" & "tar" are anagrams because if we sort those two strings, "art" & "art" are equal to one another.
Another good thought to have is, if we know a strings sorted representation we can figure out its group easily with a HashTable. If we know "rat" & "art" & tar" are all anagrams of one another, we can sort all of them in a Hashtable with their common sorted representation of "art" as HashTable key. It would look something like this:
get sorted representations of the input array...sort each element
for index of sorted
if our sorted representation is already in the HashTable
get the value, and add the element of the input array (at this index) to the hashTable value
if our sorted representation is NOT in the HashTable
add it, with a value of the element of the input array, at this index.
for values in our HashTable
append them to the return value
return the return value
This can be a little wordy on the plan english implementation but we will see it with code soon enough. The space complexity of this solution is O(wn) where w is the number of unique words, and n is the length of the longest word. The time complexity of this problem is the time it takes to sort the input array O(nLogn) times the number of words in the input array that are unique. This comes out to be O(wnLog(n)) time.
The final product:
let sorted = strs.map { String($0.sorted()) } // Our array of sorted representations
var returnVal = [[String]]()
var hashMap = [String: [String]]()
for (index, element) in sorted.enumerated() {
if var existing = hashMap[element] { // if our element is already in the HashTable
existing.append(strs[index]) // Get the grouped words, and add our new word to the existing array
hashMap[element] = existing
} else {
hashMap[element] = [strs[index]] // It is not in HashTable yet, lets add the unique string to it as a key, with our original word as the value
}
}
for value in hashMap.values { returnVal.append(value) } // For all grouped words, lets append it to our return value.
return returnVal
Well Done!
Longest Consecutive Sequence
This problem is our introduction into common leetcode problems, namely sequences and subsequences.
Brute Force
We should make sure we read the problem carefully here. There are a couple things to keep in mind:
- The numbers are unsorted
- We do not care what the longest consecutive sequence is, we just care about the length of the longest sequence
- We must have an O(n) solution
Because we need an O(n) solution, it may be a waste of our time thinking of Brute force solutions. We know also that we cannot sort this list of unsorted numbers, because sorting alone will give us, at best, O(nLogn) time complexity.
It's important here to realize what makes a sequence. If we have a number X, we know we have a sequence if X - 1 or X + 1 exists. If we wanted to think of a brute force solution, we could start by iterating on every element and looking for something that would match a sequence on each number. If we find a number, we could loop once again expanding left and right of our sequence.
for number in array
for inner number in array
if inner makes a sequence
search for expansion of left of sequence
search for expansion of right of sequence
keep track if this is the longest we have seen
return the longest we have seen
Overall this works, but has terrible efficiency. We have two nested loops, which gives us O(n²) time complexity. Plus for our expansion of the left & right of our sequence, we would continually search in our array for those. At best a searching algorithm could give us O(2Logn) because we have to do it twice. Overall this gives us O(n²Logn) time complexity. Just not great.
Approach
[ HashTable ]
[ O(n) time + O(n) space ]
Yep! You guessed it, we are bringing back our friend the hash table. We can look for the existence of a sequence as we iterate on our array. And store each value in our array to see if we have seen a possible sequence already.
for number in array
keep track of this iterative sequence length
while ± 1 of our number exists in the hashTable
append to our sequence
keep expanding in the direction we are checking
add this number to the hashTable
what is bigger, the longest sequence we have seen? or this iterative sequence length?
return longest
This is an O(n) solution, where n is the length of the input array, because we only iterate through the array once, and our while loop is just checking for the existence of a number in a hash table. Hash Table's give us O(1) lookup which is awesome. Our space is O(n) because we are just filling a hashTable, and a hashTable can only be n length where n is the number of unique numbers in our input array. Let's create the final answer:
var longest = 0 // Initially our greatest sequence will be 0
var hashMap = [Int:Bool]()
for element in nums {
var minusOne = element - 1 // Create a variable for the left section of our possible sequence
var plusOne = element + 1 // Create a variable for the right section of our possible sequence
var thisSequenceLongest = 1
while hashMap[minusOne] != nil { // While we have seen a left sequence (it exists in our hashTable)
thisSequenceLongest += 1
minusOne -= 1 // Keep expanding
}
while hashMap[plusOne] != nil { // While we have seen a right sequence (it exists in our hashTable)
thisSequenceLongest += 1
plusOne += 1 // Keep expanding
}
hashMap[element] = true // Add this element to our hashTable
longest = max(longest, thisSequenceLongest) // Update the longest sequence we have seen
}
return longest
Nice! This was definitely a tricky one.
Encode and Decode Strings
This is a LeetCode premium question, but still worth going over as it gives good insight on Array/String manipulation! This is a classic Google question too. Here is the screenshot:
Possible Ideas
Pretty straight forward! And considering there is not really a point to optimize a brute force solution lets walk through some thoughts.
1. We have to create 2 functions, an encoding function & a decoding function. The importance is how we need to encode our original array, so our decoding function will know how to handle the string. 2. We need to make this generic enough to use any ASCII characters. 3. This must be stateless. No class level variables allowed.
So when I looked at this problem, my first thought was 'I need a way to mark the separation of values in our original array'. For example if we have an input array of ["Alex", "Loves", "Google"] then I need a special character to mark the difference between "Alex" and "Google". With this thinking, I chose "#" as my separation character. ["Alex", "Loves", "Google"] would turn into → "Alex#Loves#Google". Nice!
This causes concern though. In our original problem statement, the question mentioned we need these functions to be generic enough to host any ASCII character. If we use any ASCII character as our separation element, there is the chance the separation element appears in our input array. Let's take the input array of ["Alex", "#", "R"] for example. If our separation element is "#" our input array would be encoded to "Alex###R". When we go to decode this, and decode based on separation elements, does the string "Alex###R" translate to ["Alex", "##R"]? Or ["Alex#", "#R"]? Or ["Alex#", "#", "R"]? There is no way to know. And no matter the separation character we choose to use, this will be a problem.
To solve this, we need a way to define 1. the separation of characters, and 2. the beginning and end of an element. A straight forward way to go about this is by using the word's length + separation character at the beginning of each element. For example ["Alex", "#", "R"] is encoded into "4#Alex1##1#R". The thinking here is, when we get to separation character, the previous number to it will tell us how far ahead to skip for our element. So on and so forth ad nauseam. Let's get some psuedocode together for the encoding and decoding.
Encoding:
for word in input
concatenate return string with: word length + "#" + word
return the encoded string
Decoding:
start at the beginning of the encoded string
while this index is in bounds of the string
start a new index for the current element
while this new index is not a separation character
append to new index by 1
else
get word size from index -> newIndex
get word from new index -> word size + 1
append word to response
track new index at the end of the last added word
Lot of Math there! Let's talk some time complexities. Encoding function will obviously be O(n) time where n is the length of the inout array. The space complexity will be O(c + 1 + s) where c is the number of characters in our input array, s is the separation character or string we choose, and 1 for the length of the word in Int form.
Decoding is a little more complicated. The space complexity is O(n) where n is the length of our original input array. The time complexity is O(n - x) where n is the length of characters in our encoded string, and x is the number of elements in our original input array. Not too bad.
Approach
[ Separation Characters + Length ]
[ Encoding: O(n) time, O(c + 1 + s) space ]
[ Decoding: O(n - x) time, O(n) space ]
Let's put this implementation to the test!
func encode(_ words: [String]) -> String {
var returnVal = ""
for word in words {
returnVal += "\(word.count)" + "#" + word // Pre-traversal concatenation
}
return returnVal
}
func decode(_ str: String) -> [String] {
var returnVal = [String]()
var index = 0
while index < str.count { // Loop through characters in our encoded string
var thisWordIndex = index // Index for this given word
while thisWordIndex < str.count {
let currentElementIndex = str.index(str.startIndex, offsetBy: thisWordIndex)
if str[currentElementIndex] != "#" { // While we have not found a new word, continue
thisWordIndex += 1
} else {
break // We have found a word, time to evaluate
}
}
let beginningIndex = str.index(str.startIndex, offsetBy: index)
let endingIndex = str.index(str.startIndex, offsetBy: thisWordIndex)
let wordSize = Int(str[beginningIndex..<endingIndex]) ?? 0 // The size of the word
let wordBeginningIndex = str.index(str.startIndex, offsetBy: thisWordIndex + 1)
let wordEndingIndex = str.index(str.startIndex, offsetBy: thisWordIndex + 1 + wordSize)
let word = str[wordBeginningIndex..<wordEndingIndex] // The word itself
returnVal.append(String(word)) // Append the word to our return array
index = thisWordIndex + 1 + wordSize // Set index to the end of our last word found and continue.
}
return returnVal
}
Substrings in Swift are NOT FUN 😎
Top K Frequent Elements
This is a tricky problem, especially in the iOS world.
Brute Force
I think the brute force solution is pretty obvious. We can nest loops, and for every element we can count how often it appears in the input array. Outside of our loops we can keep track of the largest count. Based on our K input integer we can build out our top k frequent elements array.
create array of k length
for indexed loop from 1 -> k
loop input array and find most indexed most element and its count
compare after each loop to see if the return array needs to be adjusted
This has two nested loops so the time complexity here would be O(nk) where n is the length of the input array, and k is the input variable k. The space complexity would be O(k) where k is the input variable k we start the problem with, due to the length of the return variable.
Even a brute force solution here would be difficult, so lets simplify our lives a little bit, and introduce our favorite friends: Sorting and A HashTable.
Approach
[ Sort + HashTable ]
[ O(uLogu) time + O(2u) space ]
One easy way to simplify storing the count of each character frequency is to use a HashTable. We can use the HashTable as an [Int:Int] dictionary where each key is the unique element in the input array, and the value is its frequency in the input array. We can then sort our dictionary by values, descending order to get which elements have the highest frequency, and return the first k from the sorted dictionary.
for number in array
add to hashTable if it doesnt already exist
if it does exist, append its frequency by 1
sort hashTable by values, descending order
for indexed loop in 1 -> k
get hashTable[index] key, and add to return array
return returnArray
The tricky thing here is to make sure you are sorting properly. We want to sort the hashTable, but after sorting we only care about the keys in the hash-table, so it might be more intelligent to leverage the swift built in higher order functions on arrays to get the data structure we want.
var hashTable = [Int:Int]()
var returnVal = [Int]()
for num in nums {
hashTable[num, default: 0] += 1 // add these values to a hashTable, and append the existing number if it exists
}
let sorted = Array(hashTable.sorted(by: { $0.value > $1.value }) // sort our hashTable by value.
.map { $0.key }) // But then put the (now sorted) keys into an array for easier access
for i in 0..<k { // loop through K times to get the top K elements from the sorted data structure
returnVal.append(sorted[i])
}
return returnVal
The time complexity here is (n + uLogu + u + k) Where K is our input variable k, and n is the size of the input array, and u is the number of unique numbers. We go through the input array once (n), we sort the hashTable (guaranteed to only have u elements -> uLogu), we add the unique elements into an array (u) and loop to find the top k elements (k). This mathematically simplifies to 2uLogu + n + k -> which translates to uLogu on average.
The space complexity is O(2u) where u is the number of unique elements in the input array. Our HashTable will only ever be u size, because all keys must be unique in a hashTable. and our array of sorted keys will only ever be u size because of the same reason as before. That is 2 separate u space data structures that on average equal out to 2u.
Well done! Just be careful when it comes to Swift sorting 😃
Container With Most Water
This is a tricky problem, especially in the iOS world.
On initial thinking we see this has a math component. The good news about programming problems with math components is, the math is never more than basic algebra. It's all about having strong problem solving skills
Brute Force
The brute force solution to this problem seems obvious at first. We need to find the largest area between two points. By having some nested loops, we can calculate all possible areas for all values.
keep track of maximum
for number in array
for inner number in array
calculate area
update maximum as necessary
The time complexity here is O(n²) due to the nested nature of the loops. Calculating area, and keeping track of a maximum are both O(1) operations. The space complexity is also constant because we are just storing the return value in a single variable, that does not expand.
Approach
[ 2 pointers ]
[ O(n) time + O(1) space ]
By using 2 pointers we can more effectively find the maximum area within a set of data points. We essentially need to find the 2 values that are the furthest apart, with one of the values being as maximum as possible. By keeping a left and right pointer and the beginning and end of our array, we can iteratively move the pointers inward based on which value is smaller. That way we can keep our maximum of the 2 values.
keep a left & right pointer
keep a maximum array variable
while left pointer < right pointer
find area
update area as needed
move either left or right pointer inward (whichever is smaller)
The time complexity here is O(1/2n) which translates to O(n) on average. This is because we will on average gravitate towards the middle of our array with our pointers. It is guaranteed we will never move greater than the length of the array. The space complexity is O(1) because we only have 3 constant variables, the area & the left + right pointers.
We should think how to find the area at each iteration. This can be found of width ** height. The height is the smaller of the 2 values because the problem description says we cannot tip our container. And the width is the distance between the 2 pointers aka rightPointer - leftPointer.
guard height.count > 1 else { return 0 } // edge cases
var leftPointer = 0, rightPointer = height.count - 1, area = 0 // setup our pointers
while leftPointer < rightPointer {
let leftValue = height[leftPointer]
let rightValue = height[rightPointer]
let iterativeArea = (rightPointer - leftPointer) * min(leftValue, rightValue) // find our area at this cycle in our loop
area = max(area, iterativeArea) // update our area value as needed
if leftValue < rightValue { // left value is smaller, move left pointer in
leftPointer += 1
} else if leftValue > rightValue { // right value is smaller, move right pointer in
rightPointer -= 1
} else { // values are equal, move both pointers
leftPointer += 1
rightPointer -= 1
}
}
return area
Conclusion
When facing array problems, try to keep in mind some of these tricks we learned in these problems. You will start to find programming problems follow similar patterns! Happy Coding!
