leetcode: 2 sum - think about DICTIONARIES

Things I learnt:

When there is mapping to be done, think about a DICTIONARY

• Here, we have to use the VALUES of the array, e.g. [1, 2, 3, 4]

  • Figure out which numbers add up to 6 = 2 + 4

• But we want to output the INDEX of the array

• So we need to map the values, 2 and 4, to their indices

• Whenever mapping is needed, think of using a DICTIONARY

When thinking about for loops and lots of iterations, think about a DICTIONARY

Brute force:

• I knew I’d need to write some for loops and call stuff again and again til I got the solution.

• I also knew this would be poorly optimized for big O notation (time and space)

• I thought I’d optimised it because I was reducing the size of the array each time, but, even still, it wasn’t great apparently.

Big O notation

• Time is more important than Space (memory / storage)

• Often, the brute force will have

  • Time = O(n²) and Space = O(1)

  • The largest possible time

  • The smallest possible space, because you’re not storing anything

• Time is MUCH more important to optimise, because memory is cheap and enormous

  • Often, there is a way to flip Time = O(n²) and Space = O(1) to Time = O(n) and Space = O(n)