cpp-flashcards/inbox.org

Inbox

• 1. two sum
• study: why min doesn't work with Fenwick tree (no inverse, update breaks on increase)
• Binary search

1. two sum

class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    vector<pair<int, int>> rev;
    // Fix 1 & 2: Loop over nums.size() and push nums[i]
    for (int i = 0; i < nums.size(); i++) {
      rev.push_back({nums[i], i});
    }

    std::sort(rev.begin(), rev.end());

    for (int i = 0; i < rev.size(); i++) {
      int want = target - rev[i].first;
      // Fix 3: Pass the SORTED vector 'rev' to the search
      int j = bs(rev, want, i + 1);
      if (j >= 0) {
        int a = rev[i].second;
        int b = rev[j].second;
        return vector<int>{min(a, b), max(a, b)};
      }
    }
    return {};
  }

  // Updated to handle vector of pairs
  using PairIter = vector<pair<int, int>>::iterator;

  PairIter lower_bound(PairIter l, PairIter r, int target) {
    while (l < r) {
      PairIter mid = l + (r - l) / 2;
      if (mid->first >= target) { // Access value via .first or ->first
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }

  int bs(vector<pair<int, int>> &indexedNums, int target, int offset) {
    auto it =
        lower_bound(indexedNums.begin() + offset, indexedNums.end(), target);
    if (it == indexedNums.end() || it->first != target) {
      return -1;
    }
    return it - indexedNums.begin();
  }
};

using PairIter = vector<pair<int, int>>::iterator; what is using?

we need to write binary search, lower bound search

learn about binary search functions the natural one by god

keep

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        bool state = false;
        int prev = 0;
        int best = 0;
        nums.push_back(0);
        for (int i=0; i<nums.size(); i++) {
            if (!state && nums[i]==1) {
                prev = i;
                state = true;
            } else if (state && nums[i]==0) {
                best = std::max(best, i-prev);
                state = false;
            }
        }
        return best;
    }
};

TODO study: why min doesn't work with Fenwick tree (no inverse, update breaks on increase)

Binary search

def bs(a, x, l, r):
    if l >= r:
        return l

    m = l + (r-l) // 2
    if (a[m] < x):
        return bs(a, x, m+1, r);
    else:
        return bs(a, x, l, m)