Can someone explain why this is O(n) time complexity?
because the array is already sorted and the two points never meet so each element is visited at most once
To improve the brute force solution, two natural questions to ask are “can we skip any pairs?” and “have we used all the unknowns?”.
Does it always work when the brute force tries to solve with two loops?
Is it possible to point to some other examples
… If we sort all two sum pairs by their sum value, the middle point is the smallest number + largest number 2 + 18 …
#sorted pairs by their sum:
[[2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5], [2, 8], [3, 8], [4, 8], [2, 11], [5, 8], [3, 11], [4, 11], [5, 11], [8, 11], [2, 18], [3, 18], [4, 18], [5, 18], [8, 18], [11, 18]]
i don’t see [2, 18] pair, to be middle point… More like a [5, 8]
Please can you properly specify the format of the output. It’s really frustrating for some of the questions where you show an example that could be interpreted in multiple ways and it’s not clear what you actually want outputted without just testing it.
Seconded!
I’ve come across a number of questions where the expected output is ambiguous, especially when viewing the “expected output” from the test cases. When test output is “1 2 3” you usually have to return an array [1,2,3]. Wish this was made more clear in the question or in how output is displayed throughout the site.