Q For Problems - Episode 10 - Leet Code #1

[jkane17]

Hi everyone,

Please check out episode 10 of the Q For Problems video series.

This covers problem 1 from the Leet Code problem set.

Leet Code #1

Given an array of integers and a target, we must return the indices of the two numbers such that they add up to the target.

Feel free to share your own solutions and ideas in the comments.

Github Repo

Thanks

[jbetz34]

Great video. I was shocked to see solution 2 perform so well as I tend to avoid while loops at all cost. I also wonder whether you could improve performance by filtering out numbers that are greater than or equal to the target (assuming there are no negative numbers).

[jbetz34]

How about this solution?

s3:{i where x=yi+yi@yi bin x-yi:y i:iasc y}

It is highly depended on there only being 1 solution as it will return all indexes that have a complimentary pair. If there were 2 pairs that add to the target, it will return 4 indexes in a list. 
If you want to retrieve multiple target pairs you will have to join the s3 results with something like:

first 2 0N#.[,’]1 reverse\ s3[x;y]

[jkane17]

Nice one, this shows significant improvement over s2

f  n     | average              mem    
---------| ----------------------------
s2 10    | 0D00:00:00.000006399 1123   
s2 100   | 0D00:00:00.000092521 4067   
s2 1000  | 0D00:00:00.000342868 19530  
s2 10000 | 0D00:00:00.013389806 223510 
s2 100000| 0D00:00:02.285027392 3356131
s3 10    | 0D00:00:00.000001701 640    
s3 100   | 0D00:00:00.000006387 4224   
s3 1000  | 0D00:00:00.000091795 32896  
s3 10000 | 0D00:00:00.001366613 524416 
s3 100000| 0D00:00:00.009052536 4194432

[jbetz34]

I think I further improved on my solution, especially at high values of n.  Incredible how simple it is. 

s4:{where y in x-y}

I also tried to reduce the memory requirements in your test case generator function. My small laptop can't afford the 10GB it takes to generate large test cases. This function seems to do the trick:

g:{(rand where 1=count each group raze n+1_(_[1]\)n;n:neg[x]?10000)}