I am suspicious that all O(nlogn) and O(n^2) solutions are dependent on data, but I cannot prove it


  • 0
    E

    I independently developed a C++ solution sharing almost exactly the same idea as this Java solution https://leetcode.com/discuss/72232/a-o-nlgn-solution

    The idea is to sort the array first, maintaining two elements: left and right, and then to use binary search to look for the middle element, gradually moving left or right element to shrink the search range.

    However, look at the following simple example,
    [-5, -5, -4, 0, 0, 3, 3, 4, 5] and search for -2.
    It is not hard to see that we can actually obtain the exact match by picking -5, 3 and 0.

    We first fix -5 and 5 and then look for -2.
    The thing is that -4 and 0 can both reach the smallest gap, so we have an ambiguity of either moving the left or right element, which makes the correctness based on the input data.
    If we choose -4 as the current middle element, then we have to move the left element.
    After two iterations, both -5 are moved out of the checking range, and we can not get the correct answer.

    The aforementioned Java implementation seems to be correct on this particular example, because it returns 0 as the mid element.
    But again this solution seems to be dependent on input data.

    If I understand correctly, all O(nlogn) and O(n^2) solutions are based on moving the left or right element, although I cannot prove it, I have a feeling that they might all share the same ambiguity.

    I hope I missed something tiny but important.
    Any one would like to comment on this?

    The code is attached as follows:

    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            if (nums.size() < 3) return 0;
            sort(nums);
            int left = 0; int right = nums.size()-1;
            int gap = INT_MAX;
            int sum3 = 0;
            while (left <= right-2) {
                int sum2 = nums[left] + nums[right];
                int third = target - sum2;
                if (binary_search(nums.begin()+left+1, nums.begin()+right, third)) {
                    return target;
                }
                // "low" is the place where the desired mid value should be
                // upper_bound() and lower_bound() should return the same place because there is no exact match
                // otherwise, binary_search() would have returned already
                auto low = lower_bound(nums.begin()+left+1, nums.begin()+right, third);
                if (low != nums.begin()+right) {
                    int newgap = abs(sum2+*low-target);
                    if (gap > newgap) {
                        gap = newgap;
                        sum3 = sum2 + *low;
                    }
                }
                if (low != nums.begin()+left+1) {
                    int newgap = abs(sum2+*(low-1)-target);
                    if (gap > newgap) {
                        gap = newgap;
                        sum3 = sum2 + *(low-1);
                    }
                }
                if (sum3 > target)
                    --right;
                else
                    ++left;
            }
            return sum3;
        }
    };

  • 0

    That's not how the O(n^2) solutions work. Have you actually looked at any? At least look at the top-voted one.


  • 0
    E

    I looked at all O(n^2) solutions at the discussion board.
    The only difference is that instead of a binary search, they do a linear search.
    But the basic pattern is the same, either move the left or right element.
    Am I missing something?

    Again, there is ambiguity if two or more element would reach the same minimum gap.
    For instance, we can test either sum3 > target or >= for moving the right element.
    This would give us some testcases covered, but it is still input data dependent.


  • 0
    E

    The real issue I see here is that either moving the left or right element depends on if it is positive or negative of the value sum3-target.
    However, if you have the positive minimum gap equals to the negative minimum gap, you can not ensure the correctness of moving that left or that right element.


  • 0

    I suggest you read the top-voted answer more carefully. I hope you'll see that it doesn't work that way. But if you then still think it's wrong, please give an example and the indexes i, j and k where you think that solution makes a mistake.


  • 0
    E

    Thanks Stefan,
    My bad that I was not careful enough.
    I read the top-voted solution again and now captured the differences.
    O(n^2) solutions do ensure checking all possible combinations.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.