Arrays Basics + STL

1. Two Sum

Mental Model:

  • Need to find two numbers adding up to a target.
  • Use a hash map for O(n) lookup instead of nested loops.
  • Store num -> index while traversing array.

C++ Solution:

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> mp;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (mp.count(complement)) return {mp[complement], i};
        mp[nums[i]] = i;
    }
    return {};
}

Revision Tip:

  • Think hash map → “store what you need to find later”.
  • Avoid nested loops for pair-sum problems.

2. Best Time to Buy and Sell Stock

Mental Model:

  • Need max profit from buy once, sell once.
  • Track minimum price so far, calculate profit at each step.

C++ Solution:

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX, maxProfit = 0;
    for (int price : prices) {
        minPrice = min(minPrice, price);
        maxProfit = max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

Revision Tip:

  • Always track running minimum/maximum when looking for single-pass solutions.

3. Contains Duplicate

Mental Model:

  • Check if any number repeats in array.
  • Hash set works in O(n) time.
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int num : nums) {
        if (seen.count(num)) return true;
        seen.insert(num);
    }
    return false;
}

Revision Tip:

  • Think hash set → uniqueness.
  • Useful for any duplicate detection problems.