To understand how to write efficient code, one of the ways is to practice. And I am now trying to use the Feynman technique to help myself tackle Computer Science.
Today, I wanna share how to complete a LeetCode problem as the progress.
My first attempt is right here.⬇️
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]My thought is running two cursors, i and j, to iterate through the list and find two indices that match the target. Time complexity is horrible here because it has a nested loop, O(n times n) = O(n²). Space complexity is excellent because I haven’t created any list/ dictionary, and it’s O(1). A great solution should not be in the red zone as below.
Try to teach someone like five:
Let say “i” and “j” is a couple, and they’re playing a game that needs them to match the sum of the value of cards they’re holding, and they need to give their positions at the end of the game. They need to find the sum of 15 to win this game.
At the first possession, Mr. i is getting number 2 on hand at position 0 (index of the list starts at 0), and the rule said they could not step on the same position. Miss j needs to walk to position 1. Miss j is getting number 6 at position 1.
Then the machine ask if they get sum of 15, but they only get 8 this time. So Miss j needs to take one more step, she gets number 9 at position 2. Now, the machine asks again, but they get 11 this time (it’s close). Oops, Miss j has reached the end, so Mr. i needs move forward to get another card to test the result. Mr. i move forward to position 1. He gets number 6 at position 1. Because Miss j is always ahead of Mr. i, she doesn’t need to move this time.
Machine asks again, finally getting a sum of 15, and they can report their location [1, 2] to the machine to win the game.
Sounds quite fast, right? Also, Mr. i, Miss j don’t need to take any notes to remember card numbers at positions. However, they need to walk more on a longer distance because they didn’t take notes on cards they read. Every time, Mr. i need to stand on a position and wait for Miss j to shout back every card number at the ahead positions to find the combination that matches the target. If there are 100 cards, Miss j will be so tired because she needs to run back and forth and shut back the card number many times. Sounds horrible, right to both of them, and they may break up because of not taking notes 😓. (Just kidding here)
So marking down numbers is important to win the game faster, and Mr. i can finish the game on his own too, but he will need a notebook, [continue]….
I will go over my second attempt tomorrow. 🙂
