Session 2

Searching & Array

Precomputation
Mastering Fundamental Competitive Programming Techniques
 Session Overview
Topics We Will Cover
● Binary Search Fundamentals
Core algorithm and implementation
Time complexity analysis
● Binary Search on Answer
Monotonic search spaces
Problem-solving patterns
● Prefix Sum & Suffix Sum Arrays
Range query optimization
2D prefix sums introduction
● Difference Array Technique
Efficient range updates
Applications in competitive programming
 Binary Search Fundamentals
What is Binary Search?
Binary Search is a divide-and-conquer algorithm that efficiently finds a target
element in a sorted array by repeatedly dividing the search interval in half.
• Time Complexity: O(log n)
• Space Complexity: O(1) for iterative, O(log n) for recursive
• Prerequisite: Array must be sorted

Core Intuition
At each step, we eliminate half of the remaining elements:
[Link] target with middle element
[Link] target equals middle → Found!
[Link] target < middle→ Search left half
[Link] target > middle→ Search right half
[Link] until found or search space is empty
 What is Binary Search?
Binary Search is a highly efficient searching algorithm that works on sorted
arrays by repeatedly dividing the search space in half.
Core Idea:
Instead of checking every element one by one, we compare the target with
the middle element and eliminate half of the remaining elements in each
step.

Time Complexity: O(log n)

This logarithmic complexity means:
• For 1,000 elements → ~10 comparisons
• For 1,000,000 elements → ~20 comparisons
• For 1,000,000,000 elements → ~30 comparisons
Compared to linear search O(n), this is exponentially faster!
 Binary Search Algorithm
The Algorithm Steps:
[Link] two pointers:
2.• low = 0 (start of array)
3.• high = n - 1 (end of array)
[Link] low <= high:
5.• Calculate mid = low + (high - low) / 2
6.• This formula prevents integer overflow

[Link] arr[mid] with target:

→
2.• If arr[mid] == target Found! Return mid
→
3.• If arr[mid] < target Search right half
[Link] low = mid + 1
→
5.• If arr[mid] > target Search left half
[Link] high = mid - 1
[Link] loop ends→ Element not found, return -1
 Binary Search Code Template
Standard Iterative Implementation
int binarySearch(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;

if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1; // Element not found
}

Key Implementation Details

• Use mid = low + (high - low) / 2 to prevent overflow
• Condition low <= high ensures all elements are checked
• Return -1 or appropriate value when element not found
• Time Complexity: O(log n)
• Space Complexity: O(1) for iterative approach
 When to Use Binary Search

Binary Search is applicable in three main scenarios:

[Link] Arrays
• When searching for a specific element
• When finding insertion position
• When counting occurrences of elements
• Array must be sorted in ascending or descending order

[Link] Functions
• Functions that are always increasing or decreasing
• Finding roots or threshold values
• Useful when f(x) changes from false to true (or vice versa)

[Link] Problems
• Minimizing the maximum value
• Maximizing the minimum value
• Finding optimal allocation or distribution
 Binary Search on Answer
What is Binary Search on Answer?
Binary Search on Answer is a powerful technique where instead of searching
for an element in an array, we search for the optimal answer in a solution
space.
Key Insight: If we can frame our problem as "find the minimum/maximum
value X such that condition(X) is true", and the condition is monotonic, we
can binary search on X.
When to Use This Technique?
• The answer lies in a continuous or discrete range [lo, hi]
• There exists a predicate function check(mid) that returns true/false
• The predicate is monotonic: if check(x) is true, then check(x+1) is also true
(or vice versa)
• Direct computation is expensive, but verification is cheap
 Key Insight: Monotonicity Property

The Core Observation:

If f(x) is true for some value x, what happens for adjacent values?
• If f(x) = true and f(x+1) = false
→ x is likely the boundary (maximum valid answer)
• If f(x) = false and f(x+1) = true
→ x+1 is likely the boundary (minimum valid answer)

Why This Matters:

This monotonic behavior creates a "transition point" in the search space:
[FALSE, FALSE, FALSE, TRUE, TRUE, TRUE]
↑
Answer lies here!
Binary search efficiently finds this transition in O(log n) time instead of
checking every value linearly.
 Binary Search on Answer Template

Step 1: Define the Search Space

• Identify the minimum possible answer (lo)
• Identify the maximum possible answer (hi)
• The answer lies somewhere in [lo, hi]
int lo = minimum_possible_value;
int hi = maximum_possible_value;

Step 2: Write the Feasibility Check Function

bool canAchieve(int mid, /* other params */) {
// Check if 'mid' is achievable
// Return true if feasible, false otherwise
}
Key Insight: This function must run in O(n) or O(n log n)
 Common Binary Search Patterns

Minimize the Maximum

This pattern appears when you need to divide resources to minimize the
worst-case scenario. Example: "Split array into K subarrays to minimize the
maximum subarray sum." Binary search on the answer (maximum sum
allowed), then greedily check if K or fewer splits achieve it.

Maximize the Minimum

Used when you want the best worst-case guarantee. Example: "Place K
cows in N stalls to maximize minimum distance between any two cows."
Binary search on the minimum distance, then greedily verify if K cows can
be placed with at least that gap between them.
 Prefix Sum & Suffix Sum Arrays

What is Prefix Sum?

A prefix sum array stores cumulative sums from the start of an array up to
each index. For array A, prefix[i] = A[0] + A[1] + ... + A[i].
Key Insight: Once computed in O(n), any range sum query [L, R] can be
answered in O(1) using: sum(L, R) = prefix[R] - prefix[L-1]

What is Suffix Sum?

A suffix sum array stores cumulative sums from each index to the end of
the array. For array A, suffix[i] = A[i] + A[i+1] + ... + A[n-1].
Use Case: Useful when queries involve sums from any position to the end,
or when combined with prefix sums for bidirectional computations.
 What is Prefix Sum?

Definition:
A Prefix Sum array is a precomputed array where each
element at index i stores the sum of all elements from
index 0 to index i in the original array.
prefix[i] = arr[0] + arr[1] + arr[2] + ... + arr[i]
 Building Prefix Sum Array
Construction Formula:
prefix[0] = arr[0]
prefix[i] = prefix[i-1] + arr[i] (for i ≥ 1)
This recurrence relation builds each prefix sum by adding the current
element to the previous prefix sum.

Time Complexity: O(n)

We iterate through the array exactly once, performing a constant-time
addition at each step.
Space Complexity: O(n)
We need an additional array of size n to store the prefix sums.
 Range Sum Queries
The Power of O(1) Range Queries
With a prefix sum array, we can answer any range sum query instantly!
Formula: sum(l, r) = prefix[r] - prefix[l-1]
This works because prefix[r] contains sum of elements from index 0 to r,
and prefix[l-1] contains sum from 0 to l-1. Subtracting removes the
unwanted prefix.

Example Walkthrough:
Original Array: [2, 4, 1, 3, 5]
Prefix Array: [2, 6, 7, 10, 15]
Query: Find sum from index 1 to 3 (elements: 4, 1, 3)
✓
Answer = prefix[3] - prefix[0] = 10 - 2 = 8
Without prefix sum: O(n) per query
With prefix sum: O(1) per query after O(n) preprocessing
 Suffix Sum Arrays
Definition:
suffix[i] = arr[i] + arr[i+1] + ... + arr[n-1]
This represents the sum of all elements from index i to the end of the array.
Suffix sums are the mirror concept of prefix sums, enabling efficient right-to-
left computations.

Building Suffix Sum Array:

for (int i = n-1; i >= 0; i--) {
if (i == n-1)
suffix[i] = arr[i];
else
suffix[i] = arr[i] + suffix[i+1];
}
Time Complexity: O(n) for construction
Space Complexity: O(n) for the suffix array
 Applications of Prefix Sum

Subarray Sum Problems

The most common application is finding the sum of any subarray in O(1)
time. Given a query for sum from index L to R, we simply compute: prefix[R]
- prefix[L-1]. This transforms problems like "count subarrays with sum equal
to K" into efficient solutions using hashmaps with prefix sums.

Equilibrium Index & Range XOR Queries

Equilibrium Index: Find index where left sum equals right sum. Using prefix
sum, check if prefix[i-1] == prefix[n] - prefix[i] for each index i.
Range XOR Queries: Similar to sum, XOR has the property that A^A = 0.
Build prefix XOR array, then XOR(L,R) = prefixXOR[R] ^ prefixXOR[L-1].
 Difference Array Technique

What is a Difference Array?

A Difference Array is a powerful technique for performing
multiple range update operations efficiently. Instead of updating
each element in a range individually, we use a clever
transformation.
Given an array A of size n, the difference array D is defined as:
• D[0] = A[0]
• D[i] = A[i] - A[i-1] for i > 0
 What is Difference Array?

Definition:
A Difference Array stores the difference between consecutive elements of
the original array.
Formula:
diff[i] = arr[i] - arr[i-1]
For the first element:
diff[0] = arr[0]
Key Insight:
Instead of storing actual values, we store how much each element differs
from its previous element.
This transformation allows us to perform range updates in O(1) time, which
would otherwise take O(n) time with a regular array.
 Range Update Operation
How to Perform a Range Update
To add a value val to all elements in range [l, r]:
Step 1: diff[l] += val
Step 2: diff[r+1] -= val
That's it! Just two operations regardless of range size.

Why This Works

• Adding val at index l means all elements from l onwards
will receive this value when we compute prefix sum
• Subtracting val at index r+1 cancels the effect for all
elements after the range, so only [l, r] is affected
• Time Complexity: O(1) per update operation
 Reconstructing the Original Array

Key Insight:
The prefix sum of the difference array gives back the updated original array.
If diff[] is our difference array, then:
arr[i] = diff[0] + diff[1] + ... + diff[i]
arr[i] = prefix_sum(diff, i)

Reconstruction Algorithm:
arr[0] = diff[0]
for i = 1 to n-1:
arr[i] = arr[i-1] + diff[i]
Time Complexity: O(n) - single pass reconstruction
This is why difference arrays are powerful: multiple O(1) updates followed
by one O(n) reconstruction.
 Time Complexity Analysis
Difference Array Complexity
Update Operation: O(1) per range update
• Only two array modifications needed: diff[l] += val and diff[r+1] -= val
• Regardless of range size, constant time operation
• Compare to naive approach: O(n) per update (must modify each element)
Reconstruction: O(n) to get final array
• Single pass prefix sum computation
• Each element computed exactly once

When to Use Difference Array?

Ideal Scenario:
• Multiple range updates (k updates) followed by single reconstruction
• Difference Array: O(k) + O(n) = O(k + n)
• Naive Approach: O(k × n) for k updates of average size n
Break-even Point:
• When k > 1, difference array starts showing benefits
• For large k and large ranges, speedup is dramatic
• Example: 10⁵ updates on array of 10⁵→ 10¹⁰ vs 2×10⁵ operations
 Problem 1: Search Insert Position

Problem Statement:
Given a sorted array of distinct integers and a target value, return the index
if the target is found. If not, return the index where it would be if it were
inserted in order.
You must write an algorithm with O(log n) runtime complexity.

Example:
Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Input: nums = [1, 3, 5, 6], target = 7
Output: 4
 Solution Approach
Using Lower Bound Binary Search
The key insight is to find the insertion point where the target would be
placed to maintain sorted order.
Algorithm Steps:
[Link] left = 0, right = n (array length)
[Link] left < right:
3.• Calculate mid = left + (right - left) / 2
4.• If arr[mid] < target: left = mid + 1
5.• Else: right = mid
[Link] left as the insertion point

Why This Works:

• Lower bound finds the first position where
arr[mid] >= target
• If target exists: returns its first occurrence
• If target doesn't exist: returns where it
should be inserted
• Time Complexity: O(log n)
• Space Complexity: O(1)
 Problem 2: Subarray Sum Equals K

Problem Statement
Given an array of integers nums and an integer k, return the total number of
subarrays whose sum equals to k.
Example:
Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation: Subarrays [1,1] at index (0,1) and (1,2) both sum to 2.

Key Insight
If prefix[j] - prefix[i] = k, then subarray (i, j] has sum k.
Rearranging: prefix[i] = prefix[j] - k
We need to count how many previous prefix sums equal (current_prefix - k).
Use a HashMap to store frequency of each prefix sum seen so far.
Time: O(n) | Space: O(n)
 Solution Approach
Key Insight: Prefix Sum + HashMap
The brute force O(n²) approach checks all subarrays. We can optimize to O(n)
using prefix sums with a hashmap.
Core Idea:
• prefix[i] = sum of elements from index 0 to i
• Sum of subarray [j+1, i] = prefix[i] - prefix[j]
• If prefix[i] - prefix[j] = k, then prefix[j] = prefix[i] - k

Algorithm Steps:
[Link]: hashmap with {0: 1}, count = 0, prefix = 0
[Link] each element nums[i]:
3.• Add nums[i] to prefix sum
4.• Check if (prefix - k) exists in hashmap
5.• If yes, add its frequency to count
6.• Store/update current prefix in hashmap
[Link] count
Why {0: 1}? Handles subarrays starting from index 0.
 HOT Problem 1: Aggressive Cows

Problem Statement (SPOJ - AGGRCOW)

Given N stalls at positions x1, x2, ..., xN and C cows, place the cows in stalls
such that the minimum distance between any two cows is maximized.
Input: N stalls with positions, C cows to place
Output: Largest minimum distance possible

Why Binary Search on Answer?

• We need to maximize the minimum distance
• The answer lies in a range: [1, max_position - min_position]
• Monotonic property: If we can place C cows with min distance D, we can
also place them with any distance < D
• Search space is monotonic → Binary Search applies!
 Solution Strategy
Binary Search on Answer Approach:
The key insight is that we can binary search on the minimum distance. If we
can place all cows with at least distance D, then we can also place them with
any distance less than D.
This creates a monotonic search space - making the problem perfect for
binary search on the answer.

Greedy Placement Check:

1. Sort all stall positions in ascending order
2. Place first cow at the first stall
3. For each subsequent cow, place it at the first stall that is at least D
distance from the last placed cow
4. If all cows are placed successfully, distance D is achievable
Time Complexity: O(N log N) for sorting + O(N log D) for binary search
 Implementation Hints
Search Space Definition:
• Lower bound: 1 (minimum possible distance)
• Upper bound: max_position - min_position
• This represents the range of possible answers
• Binary search finds the maximum valid distance

Feasibility Check (Greedy Placement):

• Sort stall positions in ascending order
• Place first cow at first stall
• For each subsequent cow, find next stall
at least 'mid' distance away
• Return true if all cows can be placed
 HOT Problem 2: Range Update Queries

Problem Statement:
Given an array of n elements (initially all zeros) and q queries. Each query
contains three integers l, r, and x. For each query, add x to all elements from
index l to r (inclusive). After all queries, print the final array.
Constraints:
• 1 ≤ n ≤ 10^6
• 1 ≤ q ≤ 10^5
•1≤l≤r≤n

Why This is HOT:

Naive approach: O(n × q) - will TLE for given constraints.
Key Insight: Use Difference Array technique!
• Instead of updating entire range, mark only boundaries
• diff[l] += x (start adding from l)
• diff[r+1] -= x (stop adding after r)
• Final array = prefix sum of difference array
Optimized Complexity: O(n + q)
 Solution Strategy
Step 1: Build the Difference Array
Create a difference array diff[] of size n+1, initialized to 0.
For each update operation (l, r, val):
• Add val to diff[l]
• Subtract val from diff[r+1]
This marks the "start" and "end" of each range update.

Step 2: Reconstruct the Final Array

Compute prefix sum of diff[] to get actual values:
for (int i = 1; i <= n; i++)
diff[i] += diff[i-1];
Time Complexity: O(1) per update, O(n) for reconstruction
Space Complexity: O(n) for the difference array
 Key Insight
Difference Array: Converting Range Updates to Point Updates
The fundamental insight behind difference arrays is transforming expensive
O(n) range update operations into efficient O(1) point update operations.

Traditional Approach:
• Adding value v to range [l, r] requires updating each element
• Time complexity: O(n) per update, O(q×n) for q updates
Difference Array Approach:
• Only update two points: diff[l] += v and diff[r+1] -= v
• Time complexity: O(1) per update, O(q + n) total
This converts range operations into boundary markers!
 Session Summary
Key Takeaways
● Binary Search: O(log n) time complexity
Reduces search space by half each iteration
Works on sorted arrays and monotonic functions
● Prefix Sum: O(1) range queries
O(n) preprocessing, unlimited O(1) queries
Sum(L, R) = prefix[R] - prefix[L-1]

● Difference Array: O(1) range updates

Add val to range [L, R] in constant time
diff[L] += val, diff[R+1] -= val
Reconstruct with prefix sum
These techniques form the foundation for
efficient algorithm design in competitive
programming. Practice the 4 problems!
 Further Practice
Online Judges for Practice:
• Codeforces - Extensive problem archive with difficulty ratings, regular
contests, and editorial solutions for Binary Search and Prefix Sum problems
• LeetCode - Curated problem sets organized by topic, great for interview
preparation with company-specific questions
• CSES Problem Set - Comprehensive collection covering all fundamental
algorithms with clean problem statements

Recommended Problem Tags to Search:

• "binary search" - Start with 800-1000 rated problems on Codeforces
• "prefix sum" / "cumulative sum" - Practice range query problems
• "difference array" - Search for range update problems
• "binary search on answer" - Look for optimization/minimize-maximize
problems
 Thank You!
Keep Practicing!