The Walkthrough: Plus One (LeetCode 66)

Zohaib Shahzad — Sun, 22 Mar 2020 22:44:20 +0000

If we’re given as an array the integer ‘123’, we simply want to increment the last digit and return the corresponding array representing that integer.
The first thing that should be pointed out is that we want to iterate via the given array backwards. A couple of edge cases that should be discussed is if the last digit of the number is ‘9’.

If we’re to encounter a case where the last digit of an integer value is ‘9’, then we set that index value to zero and then continue iterating. If not, then we’re working with a case where the last digit is anything but ‘9’ and in that case we simply increment that value of the digit and return the array of that integer.

Now if the last digits is a ‘9’. We simply set that digit to 0. The for loop will continue setting digits to ‘0’ if they’re ‘9’ and eventually will return the array. However, if we don’t return the array, that means we would have been dealing with a number that was for example: 9, 99, 999, 9999, etc. In that case, the array returned will contains all 0’s. The for loop will break in that case. We need to resize the array in that case.

Example: If we have 99, we return 100 which includes an extra digit.
When using languages like Java, we’ll have to resize the array if we’re to increment the last digit ‘9’.

Taking a look at line 9 above, that’s where we re-size the array if the last digit of the integer value is ‘9’. [digits.length + 1] basically says before our integer was ‘99’ and by adding an extra digit length to it, it now becomes ‘100’. We add one digit size to the array which then sets all values in the array to ‘0’ by default.

Direct your attention to line 11. Line 11 would be how we re-size the array in Javascript. Destructuring array’s have many benefits and but destructuring as a whole is an article for another day. [1, …digits] basically says we’re inserting a digit value of ‘1’ in front of whatever the rest of the integer value is.

Example: If we were dealing with [9, 9], we would end up increasing each digit value to [0, 0]. We would then add another placeholder of 1 to the beginning: [1, 0, 0].

The Walkthrough: Two Sum (LeetCode 1)

Zohaib Shahzad — Sun, 22 Mar 2020 22:29:02 +0000

Let’s start with the example given in the LeetCode problem. Suppose we’re given the array [2, 7, 11, 18] and a target value of 9. We’re tasked with finding two number within the array that add up to the target and then return the indices of those respective number.

Approach #1: Brute Force (Naive)

The naive approach typically involves using two nested for loops. How would we use them to solve the problem? Begin by iterating via the array starting with the zero index and we’ll have another for loop nested within which starts with the first index (j = i + 1). We’ll iterate through the rest of array and for every value within that array, we’ll check if any of those values is the complement to the value in the zero index.

Key: loop via each element (x) and if there is another value that equals to (target — x).

Figure 1: Having ‘j’ start at index 1, we have it iterate via the rest of the array and check if any of those values is the complement to the value where index ‘i’ is pointing to. If it is, then nums[i] + nums[j] = target. If not, then increment the ‘i’ pointer by 1 and then run through the 2nd for loop again, etc.

Time Complexity: O(n²) — For each element, we try to find its complement by looping via the rest of the array which takes O(n) time

Space Complexity: O(1)

Approach #2: Two Pass Hash Table

When talking about a more real world and optimal solution, a brute force solution just doesn’t cut it.

This is where data structures come into play.

In order to improve our run-time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. Writing an algorithm with nested for-loops is a no no at this point. The best way to maintain a mapping of each element in the array to its index? A hash table.

Implementing a hash table can reduce the look-up time from O(n) to O(1) by trading space for speed.

A hash table is built recently for this purpose, it supports fast look up in near constant time. We say “near” constant time because if a collision occurred, a lookup could be degenerated to O(n) time. However, lookup’s in hash tables should be amortized O(1) as long as the hash table was chosen carefully.

A simple implementation uses two iterations of the array. In the first iteration, we add each elements value and its index to the table (which makes sense because hash table accept key-value pairs (K, V)). In the second iteration we then check if each element’s complement (target — nums[i]) exists in the same.

NOTE: the complement must not be nums[i] itself.

Time Complexity: O(n) — each lookup cost only O(1)

Space Complexity: O(n)

Approach #3: One Pass Hash Table

As the approach suggests, this solution will implement a one pass hash table. While we iterate through the array and insert the elements into the table, we can also look back to check if the current element’s complement already exists in the table. If it exists, we have found a solution and return it immediately.

Time Complexity: O(n) — traverses list iterating n elements only once. Each lookup is O(1) constant time.

Space Complexity: O(n) — Extra space required depends on the number of items in the hash table which stores at most, n elements.

DEV Community: Zohaib Shahzad

The Walkthrough: Plus One (LeetCode 66)

The Walkthrough: Two Sum (LeetCode 1)

Approach #1: Brute Force (Naive)

Approach #2: Two Pass Hash Table

Approach #3: One Pass Hash Table