3 ms·
Sorting provides a alternative solution: sort the array, and then traverse a linear path over pairs of indices from (0,n-1) to (n-1,0) whose sum straddles the t
by tromp 3y ago
Sorting provides a alternative solution: sort the array, and then traverse a linear path over pairs of indices from (0,n-1) to (n-1,0) whose sum straddles the target:
int main() {
/* read in and sort array a */
int i=0,j=N-1, sum;
while ((sum = a[i] + a[j]) != tgt) {
if (sum < tgt)
i++;
else
j--;
}
printf("%d %d\n", i, j);
}
- colejohnson66 3y agoThe hashmap solution here is ideally O(n) as you only iterate once (assuming O(1) lookups and inserts in the map). A sort/search method, even using quicksort would be O(n*logn).
- tromp 3y agoYou can use radix sort which is linear for fixed width ints.
- jjgreen 3y agoO(n log n + n) = O(n log n)
- tromp 3y agoAlthough hashmaps are O(n) in practice, they can be worse than O(n log n) on some rare inputs that cause lots of hash collisions. Several sorting algorithms such as mergesort and heapsort are guaranteed O(n log n).
- enedil 3y agoEven it it was O(1) not amortized, it's not possible to beat the sorting in actual execution time for reasonable inputs (less than 10B elements probably)
- topposter32 3y agoWhat's log base 2 of a million or a billion?
- nkurz 3y agoI think it's a little trickier than that, since the problem asks for the indices not the numbers, which would be lost in the sorted version. You'd have to keep an additional mapping from the sorted to original positions. And are we counting the sorting and space for the maps as free? Or do we have to account for them somehow? Mostly, I just don't like the problem specification. What does it actually mean to "solve it efficiently"? How many times are we going to be searching each input array? How much memory do we have available? What tradeoff between memory and computation is allowable? How much does a comparison cost us versus accessing memory? Are all targets equally likely? Assuming as theoretical computer scientists tend to do that we can ignore all constant time operations, that access to memory is free, that an unknown but fixed amount memory is available, and that we'll be searching the same array forever ruins the problem for me. Fill in the numbers and we can talk about what's optimal, but the "spherical cow" approach does nothing for me.
- tromp 3y ago> I think it's a little trickier than that, since the problem asks for the indices not the numbers, which would be lost in the sorted version. Good point. > You'd have to keep an additional mapping from the sorted to original positions. It's simpler to just find the two numbers in the original unsorted array.
- raverbashing 3y ago> You'd have to keep an additional mapping from the sorted to original positions. 2*O(n) is still O(n)
- taeric 3y agoThough, at the low level, it is perfectly valid to compare the full costs, not just the growth rates. Right?
- deleted 3y ago[deleted]
- marginalia_nu 3y agoFor an input array of values I[], create an array A = [ 0 ... n ] so that n = len(I). Sort the indices in A based on their corresponding value in I. Now A is the mapping, A[n] is the index in I of the n+1:th largest value, and you can binary search in the same way, by comparing I[A[i]]. This is strictly more space efficient than a hash table. You're not going to win any awards for being cache efficient, but then again, when the competition is a damn hash table it's not too bad ;P