Time Complexity Calculation

The core concept involves determining the relationship between loop iterations and execution count. For nested loops, analyze the inner loop's operations relative to the outer loop's progression, then sum these operasions at critical bounds (often forming arithmetic or geometric series).

Binary Search Implementation

For sorted arrays without duplicates, search within [low, high) boundaries:

int binarySearch(std::vector<int>& arr, int key) {
    int low = 0;
    int high = arr.size();
    while (low < high) {
        int mid = low + ((high - low) >> 1);
        if (arr[mid] > key) {
            high = mid;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

Fast-Slow Pointers Technique

Removes specified values in-place by maintaining separate scan/write positions:

int filterElements(std::vector<int>& data, int excludeVal) {
    int writeIdx = 0;
    for (int readIdx = 0; readIdx < data.size(); ++readIdx) {
        if (data[readIdx] != excludeVal) {
            data[writeIdx++] = data[readIdx];
        }
    }
    return writeIdx;
}

Two-Pointer Array Processing

Squares and sorts non-decreasing arrays by comparing endpoint magnitudes:

std::vector<int> squareAndSort(std::vector<int>& input) {
    int len = input.size();
    std::vector<int> output(len);
    int left = 0;
    int right = len - 1;
    int fillPos = len - 1;

    while (left <= right) {
        int leftSq = input[left] * input[left];
        int rightSq = input[right] * input[right];
        if (leftSq > rightSq) {
            output[fillPos--] = leftSq;
            left++;
        } else {
            output[fillPos--] = rightSq;
            right--;
        }
    }
    return output;
}

Division via Bit Shifting

Right-shift operator provides efficient division for powers of two:

• Positive integers: n >> 1 ≡ n / 2 (faster execution)
• Negative integers:
  • -9 / 2 = -4 (truncates toward zero)
  • -9 >> 1 = -5 (floor division)