leetcode/daily149.cpp at main · iFangg/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// Solutiuon 1 - FAIL
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        /*
        sort
        two pointer approach
        start with left and right
        if left + right > upper, right --
        if left + right < lower, left ++
        else total ++
        return total
        */
        std::sort(nums.begin(), nums.end());
        int l = 0;
        int r = nums.size() - 1;
        long long total = 0;

        while (r >= 0) {
            std::cout << l << " - " << r << std::endl;
            if (l >= r) {
                r--;
                l = 0;
                continue;
            }

            auto sum = nums[l] + nums[r];

            if (sum > upper) {
                r--;
                l = 0;
            } else if (sum < lower)
                l++;
            else {
                l++;
                total++;
            }
        }

        return total;
    }
};


// Solution 2 - FAIL
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        /*
        sort
        two pointer approach
        start with left and right
        if left + right > upper, right --
        if left + right < lower, left ++
        else total ++
        NO

        BINARY SEARCH
        keep mid point
        if left + right > upper, right = mid - 1
        if left + right < lower, left = mid + 1
        else add (right - left)
        return total
        */
        std::sort(nums.begin(), nums.end());
        int l = 0;
        int r = nums.size() - 1;

        while (l < r) {
            std::cout << l << " - " << r << std::endl;
            auto sum = nums[l] + nums[r];
            auto mid = l + (r - l) / 2;

            if (sum > upper)
                r = mid;
            else if (sum < lower)
                l = mid;
            else
                return r - l;
        }

        return 0;
    }
}


// Solution 3
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        std::sort(nums.begin(), nums.end());
        long long total = 0;

        // i is the number in the index we are finding pairs for
        // we then find pairs of (i, n) using binary search to find how many pairs exist using start index i
        for (int i = 0; i < nums.size(); i++) {
            int l = i + 1;
            int r = nums.size() - 1;

            // Find the first position where nums[i] + nums[l] >= lower
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (nums[i] + nums[mid] >= lower)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            int leftBound = l;

            // Find the first position where nums[i] + nums[l] > upper
            l = i + 1;
            r = nums.size() - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (nums[i] + nums[mid] > upper)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            int rightBound = r;

            // Count pairs in range
            if (leftBound <= rightBound)
                total += rightBound - leftBound + 1;
        }
        return total;
    }
};