1. Two Pointers

• What is Two Pointers Technique?
  • A technique for iterating two monotonic pointers across an array to find a pair satisfying a condition in linear time.
  • Optimizes brute force by tracking the start and end of intervals or two values in an array.

Examples:

• Two-Sum Problem:

  • Problem: Given a sorted array and a target, find if two values sum up to the target.

  • Initial Brute Force:

    bool twoSum(vector<int>& A, int T) {
        for (int i = 0; i < A.size(); ++i) {
            for (int j = i + 1; j < A.size(); ++j) {
                if (A[i] + A[j] == T) return true;
            }
        }
        return false;
    }
    

    • Time Complexity: O(N^2)

  • Optimized with Two Pointers:

    bool twoSum(vector<int>& A, int T) {
        int j = A.size() - 1;
        for (int i = 0; i < j; ++i) {
            while (j > i && A[i] + A[j] > T) --j;
            if (A[i] + A[j] == T) return true;
        }
        return false;
    }
    

    • Time Complexity: O(N)
• Subarray Sum Problem:

  • Problem: Find a subarray whose sum equals a target in an unsorted array.

  • Optimized Solution:

    void subarraySum(vector<int>& A, int T) {
        int S = 0, E = 0, sum = 0;
        while (S < A.size()) {
            while (E < A.size() && sum + A[E] <= T) {
                sum += A[E++];
            }
            if (sum == T) {
                cout << S << " " << E - 1 << "\\\\n";
                return;
            }
            sum -= A[S++];
        }
        cout << -1 << "\\\\n";
    }
    

    • Time Complexity: O(N)

2. Binary Search

• Motivation

  • Efficiently find elements in sorted arrays by halving the search space with each comparison.

• Guessing Game:

  • Concept: Using binary search to guess a number between 1 and 100.

    int BinarySearch(int n, int T) {
        int l = 1, r = n, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (T == mid) return mid;
            else if (T < mid) r = mid - 1;
            else l = mid + 1;
        }
        return -1;
    }
    

    • Time Complexity: O(log2(n))

• Basic Binary Search:

  • Problem: Find the index of a value T in a sorted array.

    int BinarySearch(vector<int>& A, int T) {
        int l = 0, r = A.size() - 1, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (A[mid] == T) return mid;
            else if (A[mid] < T) l = mid + 1;
            else r = mid - 1;
        }
        return -1;
    }
    

• Rotated Sorted Array:

  • Problem: Find the minimum in a rotated sorted array.

    int findMinimum(vector<int>& A) {
        int l = 0, r = A.size() - 1, mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (A[mid] > A[r]) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    

• Binary Search on Answer:

  • Problem: Find a value x such that f(x) is closest to a target value t.

    int upperBound(int a, int b, int t) {
        int l = a, r = b, mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (f(mid) <= t) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    

    • This method optimizes searching for a value within a given range using binary search.

To Solve:

• Counting Kangaroos is Fun
• Bashar and the Bad Land (Hard)
• Magic Powder - 2