1

I am trying to solve a problem on BinarySearch.com:

Given a list of integers nums sorted in ascending order and an integer k, return whether any two elements from the list add up to k. You may not use the same element twice. Note: Numbers can be negative or 0. This should be done in O(1) space.
So for nums = [1, 3, 5, 8] and k = 6, answer should be true.

I know it can be done using two pointers, but I am learning binary search, so I came up with the following logic:

bool solve(vector<int>& nums, int k) {
    for(int i=0; i<nums.size(); i++) {
        auto loc=lower_bound(begin(nums), end(nums), k-nums[i]);
        if(loc!=nums.end()) {
            if(distance(nums.begin(), loc)!=i && *loc+nums[i]==k) return true;
        }
    }
    return false;
}

It gets accepted, but what is the time complexity? I am not sure if it is O(NlogN) since I run binary search (an O(logN) algo) for each value in nums, or if it should be O(N^2) because when the if condition is true, I use distance(), which, as I understand, is an O(n) operation by itself.

Someone
  • 611
  • 4
  • 13
  • 1
    @Someone: For a std::vector, `std::distance` is a constant-time operation. – AndyG Aug 20 '21 at 15:30
  • @AndyG, cool, thanks! – Someone Aug 20 '21 at 15:35
  • Improvements: `*loc+nums[i]==k` is always true since you just found `*loc == k - nums[i]` by searching. You also don't need to search through the entire vector; start at `begin(nums) + i + 1`. This would also make your other condition unnecessary. – molbdnilo Aug 20 '21 at 15:37
  • @YvesDaoust, sorry that was a typo. I meant: "I run binary search (an O(logN) algo) N times). – Someone Aug 20 '21 at 15:39
  • @molbdnilo: improving this version makes little sense, as you can solve the problem without any binary search. –  Aug 20 '21 at 15:41
  • @molbdnilo, I think we _do need_ that `*loc+nums[i]==k`, otherwise this test case fails: `nums = [1, 3, 5, 8]` `k = 7`. I think that's because if the element (k-nums[i]) is not found, `lower_bound` returns the next one. – Someone Aug 20 '21 at 15:42
  • @Someone No, [it works fine](http://coliru.stacked-crooked.com/a/594594ebbff454a7). – molbdnilo Aug 20 '21 at 15:46
  • @molbdnilo, oh, along with starting the search at `std::begin(nums)+i+1`, yep. :) – Someone Aug 20 '21 at 15:47

1 Answers1

7

As noted in comments in worst case the code iterates over the array and performs binary search on the array in each step. And so the complexity of that operation is O(Nlog(N)).

I use distance(), which, as I understand, is an O(n) operation by itself.

Actually it is O(1) when used on std::vector::iterator because it is a LegacyRandomAccessIterator ( Is std::next for vector O(n) or O(1)? ) and for such iterators std::distance is O(1) and so it doesn't participate in our calculation.

freakish
  • 54,167
  • 9
  • 132
  • 169