Intro: I am a former accountant turned software engineer graduated from coding bootcamp in January 2022. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.
Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.
Problem#1. Two Sum
Difficulty: Easy
Language: JavaScript
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?
Solution 1 (nested loop) with Explanation:
var twoSum = function(nums, target) {
for (i = 0; i < nums.length; i++) {
/*Loop through nums array (note 1) from position 0*/
for (j = i + 1 ; j < nums.length; j++)
/*Loop through nums array (note 1) from position 1 and add up
every possible pair of numbers until they add up to target number.
*/
if(nums[i] + nums[j] == target)
/*For example, if nums = [2,3,4], the possible pairs would be 2+3,
2+4 (starting from first number 2 add the next numbers). That was
all pairs with the number 2. Then pair 3+4 (starting from second
number 3, add the next numbers).*/
return [i, j]
/*return indices for the pairs found*/
}
};
Solution 1 Submission detail as of 2/11/2022
(Data below could vary since there are new submissions daily)
- Runtime: Runtime: 224 ms
- Memory Usage: Memory Usage: 42.5 MB
Solution 2 (object) with Explanation:
var twoSum = function(nums, target) {
let hash = {};
/*create a object (note 2) and utilize object's property value and
property key*/
for(let i = 0; i < nums.length; i++) {
/*Loop through "nums" array and find desired value to store in the
"hash" object */
const n = nums[i];
/*create a variable n to represent each number in the "nums"
array*/
if(hash[target - n] !== undefined) {
/*find the complementary pair for "n" in "hash" object*/
return [hash[target - n], i];
/*if found, return index of both the complementary pair and "n".
We can access object properties using a square bracket
object[property]*/
}
hash[n] = i;
/*If complementary pair for "n" is not found in "hash", store n
and its index in "hash".
Example Input: nums = [2,7,5,11]; target = 9. The first "n" is 2
and since "hash" is initially empty, we won't find the
complementary pair（target - n）= 7 in there. Hence, we store it in
"hash" with the index of the number 2, which is 0. And now our
"hash" is { '7', 0 } (Key is'7' and value is 0 in this object).
Then we exam if complementary pair of the second number 7 can be
found in the "hash". Since we just stored 7 in the previous step,
it will be found in this step. Therefore, we return the value that
has key of '7' in the object: hash[target - n]. And the index of
second number '7':[i]. That is [0,1]. And this is the output of
this example*/
}
}
Solution 2 Submission detail as of 2/12/2022
(Data below could vary since there are new submissions daily)
- Runtime: 88 ms
- Memory Usage: Memory Usage: 42.6 MB ******************************************
References:
LeetCode Problem Link
LeetCode Discussion
Note 1: For...Loop
Note 2: JavaScript Hash Table
Note 3: For...Loop
Youtube: ThinkFWD
Blog Cover Image Credit
Top comments (0)