Advanced Techniques

Sliding Window Technique

Fixed Size Sliding Window

The sliding window technique uses two pointers to create a "window" that slides through the data structure, typically used for subarray/substring problems.

🪟 Real-Life Analogy:

Think of looking through a window on a moving train. As the train moves, you see different scenery through the same window frame. The window size stays the same, but the content changes.

🎯 When to Use Sliding Window:

Subarray/Substring problems: Finding optimal contiguous sequences
Fixed or variable window size: Depending on problem constraints
Optimization problems: Maximum, minimum, or target sum
String matching: Pattern finding with constraints

Problem Type	Time Complexity	Space Complexity
Fixed Window	O(n)	O(1)
Variable Window	O(n)	O(k) where k is unique elements
Min Window Substring	O(n + m)	O(m) where m is pattern length

Backtracking

Systematic Solution Exploration

Backtracking is a systematic method for solving problems by trying partial solutions and abandoning them if they cannot lead to a complete solution.

🧩 Real-Life Analogy:

Think of solving a maze. You try a path, and if you hit a dead end, you backtrack to the last decision point and try a different route. You systematically explore all possibilities.

🎯 Backtracking Template:

Choose: Make a choice from available options
Explore: Recursively explore the consequences
Unchoose: Undo the choice (backtrack) if it doesn't work
Base Case: Stop when solution is found or impossible

Greedy Algorithms

Local Optimal Choices

Greedy algorithms make the locally optimal choice at each step, hoping to find a global optimum. They work when the problem has optimal substructure and the greedy choice property.

🍯 Real-Life Analogy:

Think of a bee collecting nectar. At each flower, it chooses the one with the most nectar nearby (local optimum), trusting this strategy will maximize total nectar collected (global optimum).

TypeScript

// Activity Selection Problem
function activitySelection(start: number[], finish: number[]): number[] {
    const n = start.length;
    const activities = Array.from({length: n}, (_, i) => ({index: i, start: start[i], finish: finish[i]}));
    
    // Sort by finish time
    activities.sort((a, b) => a.finish - b.finish);
    
    const selected: number[] = [];
    selected.push(activities[0].index);
    let lastFinish = activities[0].finish;
    
    for (let i = 1; i < n; i++) {
        if (activities[i].start >= lastFinish) {
            selected.push(activities[i].index);
            lastFinish = activities[i].finish;
        }
    }
    
    return selected;
}

// Fractional Knapsack
interface Item {
    value: number;
    weight: number;
    ratio: number;
}

function fractionalKnapsack(values: number[], weights: number[], capacity: number): number {
    const items: Item[] = values.map((value, i) => ({
        value,
        weight: weights[i],
        ratio: value / weights[i]
    }));
    
    // Sort by value-to-weight ratio (descending)
    items.sort((a, b) => b.ratio - a.ratio);
    
    let totalValue = 0;
    let remainingCapacity = capacity;
    
    for (const item of items) {
        if (remainingCapacity >= item.weight) {
            // Take the whole item
            totalValue += item.value;
            remainingCapacity -= item.weight;
        } else {
            // Take fraction of the item
            totalValue += item.value * (remainingCapacity / item.weight);
            break;
        }
    }
    
    return totalValue;
}

// Coin Change (Greedy - works for standard coin systems)
function coinChangeGreedy(coins: number[], amount: number): number[] {
    coins.sort((a, b) => b - a); // Sort in descending order
    const result: number[] = [];
    
    for (const coin of coins) {
        while (amount >= coin) {
            result.push(coin);
            amount -= coin;
        }
    }
    
    return amount === 0 ? result : [];
}

// Example usage
console.log(activitySelection([1, 3, 0, 5, 8, 5], [2, 4, 6, 7, 9, 9])); // [0, 1, 3, 4]
console.log(fractionalKnapsack([60, 100, 120], [10, 20, 30], 50)); // 240
console.log(coinChangeGreedy([25, 10, 5, 1], 67)); // [25, 25, 10, 5, 1, 1]

Python

# Activity Selection Problem
def activity_selection(start, finish):
    n = len(start)
    activities = [(finish[i], start[i], i) for i in range(n)]
    
    # Sort by finish time
    activities.sort()
    
    selected = [activities[0][2]]  # Select first activity
    last_finish = activities[0][0]
    
    for i in range(1, n):
        if activities[i][1] >= last_finish:  # start >= last_finish
            selected.append(activities[i][2])
            last_finish = activities[i][0]
    
    return selected

# Fractional Knapsack
def fractional_knapsack(values, weights, capacity):
    items = [(values[i] / weights[i], values[i], weights[i]) for i in range(len(values))]
    
    # Sort by value-to-weight ratio (descending)
    items.sort(reverse=True)
    
    total_value = 0
    remaining_capacity = capacity
    
    for ratio, value, weight in items:
        if remaining_capacity >= weight:
            # Take the whole item
            total_value += value
            remaining_capacity -= weight
        else:
            # Take fraction of the item
            total_value += value * (remaining_capacity / weight)
            break
    
    return total_value

# Coin Change (Greedy - works for standard coin systems)
def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)  # Sort in descending order
    result = []
    
    for coin in coins:
        while amount >= coin:
            result.append(coin)
            amount -= coin
    
    return result if amount == 0 else []

# Job Scheduling
def job_scheduling(jobs):  # jobs = [(profit, deadline)]
    # Sort by profit (descending)
    jobs.sort(key=lambda x: x[0], reverse=True)
    
    max_deadline = max(job[1] for job in jobs)
    schedule = [None] * max_deadline
    total_profit = 0
    
    for profit, deadline in jobs:
        # Find latest available slot before deadline
        for slot in range(min(deadline - 1, max_deadline - 1), -1, -1):
            if schedule[slot] is None:
                schedule[slot] = (profit, deadline)
                total_profit += profit
                break
    
    return schedule, total_profit

# Example usage
print(activity_selection([1, 3, 0, 5, 8, 5], [2, 4, 6, 7, 9, 9]))  # [0, 1, 3, 4]
print(fractional_knapsack([60, 100, 120], [10, 20, 30], 50))  # 240.0
print(coin_change_greedy([25, 10, 5, 1], 67))  # [25, 25, 10, 5, 1, 1]

OCaml

(* Activity Selection Problem *)
let activity_selection start finish =
  let n = Array.length start in
  let activities = Array.mapi (fun i _ -> (finish.(i), start.(i), i)) start in
  
  (* Sort by finish time *)
  Array.sort (fun (f1, _, _) (f2, _, _) -> compare f1 f2) activities;
  
  let selected = ref [activities.(0) |> fun (_, _, i) -> i] in
  let last_finish = ref (activities.(0) |> fun (f, _, _) -> f) in
  
  for i = 1 to n - 1 do
    let (finish_time, start_time, index) = activities.(i) in
    if start_time >= !last_finish then (
      selected := index :: !selected;
      last_finish := finish_time
    )
  done;
  
  List.rev !selected

(* Fractional Knapsack *)
let fractional_knapsack values weights capacity =
  let n = Array.length values in
  let items = Array.mapi (fun i _ -> 
    (float_of_int values.(i) /. float_of_int weights.(i), values.(i), weights.(i))
  ) values in
  
  (* Sort by value-to-weight ratio (descending) *)
  Array.sort (fun (r1, _, _) (r2, _, _) -> compare r2 r1) items;
  
  let total_value = ref 0.0 in
  let remaining_capacity = ref capacity in
  
  for i = 0 to n - 1 do
    let (ratio, value, weight) = items.(i) in
    if !remaining_capacity >= weight then (
      (* Take the whole item *)
      total_value := !total_value +. float_of_int value;
      remaining_capacity := !remaining_capacity - weight
    ) else if !remaining_capacity > 0 then (
      (* Take fraction of the item *)
      total_value := !total_value +. (float_of_int value *. float_of_int !remaining_capacity /. float_of_int weight);
      remaining_capacity := 0
    )
  done;
  
  !total_value

(* Coin Change (Greedy) *)
let coin_change_greedy coins amount =
  let sorted_coins = List.sort (fun a b -> compare b a) coins in
  let result = ref [] in
  let remaining = ref amount in
  
  List.iter (fun coin ->
    while !remaining >= coin do
      result := coin :: !result;
      remaining := !remaining - coin
    done
  ) sorted_coins;
  
  if !remaining = 0 then List.rev !result else []

(* Example usage *)
let start_times = [|1; 3; 0; 5; 8; 5|]
let finish_times = [|2; 4; 6; 7; 9; 9|]
let selected_activities = activity_selection start_times finish_times

let values = [|60; 100; 120|]
let weights = [|10; 20; 30|]
let max_value = fractional_knapsack values weights 50

let coins = [25; 10; 5; 1]
let change = coin_change_greedy coins 67

🎯 When Greedy Works:

Optimal Substructure: Problem can be broken into subproblems
Greedy Choice Property: Local optimum leads to global optimum
No Dependencies: Choices don't affect future options
Sorting Often Helps: Arrange data to make greedy choice obvious

Problem	Time Complexity	Space Complexity
Activity Selection	O(n log n)	O(1)
Fractional Knapsack	O(n log n)	O(1)
Coin Change (Greedy)	O(n)	O(1)

DSA Interview Guide

Advanced Techniques

🎯 When to Use Sliding Window:

🎯 Backtracking Template:

🎯 When Greedy Works: