DSA Logic Building Playbook

Har coding session shuru karne se pehle ye 5 rules dimag me baitha lo. Zyada log DSA me code nahi, logic me atakte hain — ye guide logic banana sikhati hai.

Har problem pe ye structured sequence follow karo. Total lagbhag 16 minute — isme se 7 minute sirf soch-vichar, code uske baad.

Problem padhte hi apne aap se ye 5 basic sawal poochho:

Output type se hint

Output ka structure hi aksar data structure reveal kar deta hai:

Method: Insaan ki tarah solve karo (bina computer, bina code)

Example: Maximum Subarray Sum

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]  |  Expected output: 6

• Pehla element -2 → running sum = -2.
• Agla element 1 → pichhla sum negative hai (-2), usko saath leke chalna nuksan hai. Naya sum 1 se fresh start.
• -3 aaya → sum = 1 + (-3) = -2. Phir negative, restart ready rakho.
• 4 aaya → fresh start sum = 4. Aage -1, 2, 1 jodte gaye → running sums: 3, 5, 6.
• Max dekha = 6.

public int maxSubArray(int[] nums) {
    int cur = nums[0], best = nums[0];

    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]);        // restart ya jodte jao
        best = Math.max(best, cur);
    }
    return best;
}

Chhote input se bade ki taraf jao

• Pehle bahut chhota input (2–3 elements) pe pen-paper solve karo.
• Phir thoda medium input pe test karo.
• Dekho tumhara tareeka kahan fail ho raha hai — wahi failure point tumhe asli edge-case logic sikhata hai.

Apne khud ke test cases banao

Sirf question ke diye test case pe rely mat karo: empty/single element [] [5], sab identical [2,2,2,2], sorted / reverse sorted [1,2,3] [3,2,1], all negative [-5,-2,-9], aur max constraint limit.

Jab logic bilkul na soojh raha ho, sample test case ko in 6 nazron se dekho:

Fill-in-the-blank template

Har tough problem pe ye 7 sentences complete karo. Agar sab fill ho gaye to logic ban chuka hai — bas syntax likhna bacha hai.

Brute force ek safety net hai. Ye prove karta hai ki tumhe problem 100% samajh aa chuki hai.

Ye table memorise kar lo. Problem me n dekhte hi pata chal jata hai ki kitni fast solution chahiye.

Problem statement ke words me hi solution ka hint chhupa hota hai.

Master pattern decision tree

Direct keyword to pattern table

Ye 11 patterns DSA ke 90% interview problems solve karte hain. Har pattern ka core intuition samjho aur code template yaad rakho.

9.1 Two Pointers

• Core idea: Do pointers (l, r) ko opposite ends ya same direction se move karo, nested loops se bacho.
• Kab lagayein: Sorted array, pair sum, palindrome check, in-place array reverse.

int l = 0, r = arr.length - 1;
while (l < r) {
    int sum = arr[l] + arr[r];
    if (sum == target) {
        // target pair mil gaya
        break;
    } else if (sum < target) {
        l++;
    } else {
        r--;
    }
}

9.2 Sliding Window

• Core idea: Ek dynamic window [l, r] maintain karo. Right pointer badhao; condition violate ho to left se shrink karo.
• Kab lagayein: "Longest ya shortest contiguous subarray / substring jisme koi condition satisfy ho."
• Flow: EXPAND (arr[r] include) → window valid? nahi to SHRINK (arr[l] hatao, l++) → RECORD (best = max(best, len)).

int l = 0, best = 0;
for (int r = 0; r < n; r++) {
    // 1. arr[r] ko current window me include karo

    // 2. jab tak window invalid ho, shrink from left
    while (/* window invalid condition */ false) {
        // arr[l] ko window se hatao
        l++;
    }

    // 3. valid window size record karo
    best = Math.max(best, r - l + 1);
}

9.3 Prefix Sum

• Core idea: Running cumulative sum pehle store kar lo, taaki kisi bhi range [l, r] ka sum O(1) me mile.

int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}
// Range sum for arr[l..r]: sum = prefix[r + 1] - prefix[l]

9.4 HashMap

• Core idea: Expensive O(n) linear search ko O(1) lookup me badal do. "Pehle kaunsa element dekha tha" yaad rakho.

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
    int complement = target - arr[i];
    if (map.containsKey(complement)) {
        // pair mil gaya: indices i and map.get(complement)
    }
    map.put(arr[i], i);
}

9.5 Binary Search

• Core idea: Har step pe search space ko exactly aadha kar do.
• Kab lagayein: Sorted data me target dhoondna, ya answer monotonic ho jisme check(x) yes/no return kare.

int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;        // integer overflow protection

    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}
return -1;

9.6 Stack

• Core idea: Last-In-First-Out. Jo element sabse recent aaya, uski state sabse pehle resolve karni ho.
• Kab lagayein: Valid Parentheses, Next Greater Element, Daily Temperatures.

Deque<Character> stack = new ArrayDeque<>();
for (char ch : s.toCharArray()) {
    if (ch == '(' || ch == '{' || ch == '[') {
        stack.push(ch);
    } else {
        if (stack.isEmpty()) return false;
        char top = stack.pop();
        if ((ch == ')' && top != '(') ||
            (ch == '}' && top != '{') ||
            (ch == ']' && top != '[')) {
            return false;
        }
    }
}
return stack.isEmpty();

9.7 Recursion and Backtracking

• Core idea: Choice lo, aage explore karo, galat rasta nikla to wapas aakar step undo karo. 3 mantras: Choose → Explore → Undo.

void solve(List<Integer> path) {
    if (/* base case reached */ false) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int choice : choices) {
        path.add(choice);              // 1. Choose
        solve(path);                   // 2. Explore
        path.remove(path.size() - 1); // 3. Undo (Backtrack)
    }
}

9.8 Dynamic Programming (DP)

• Core idea: Bade problem ko chhote overlapping subproblems me todo aur results cache (memoize / table) kar lo, taaki recalculation zero ho.
• DP kaise pehchano: "Count number of ways", "Min / Max value", "Is it possible?" + har element pe choice (include / exclude).

9.9 BFS and DFS

• BFS (Queue): level-by-level traversal. Unweighted graphs me shortest path guarantee karta hai.
• DFS (Recursion / Stack): ek raaste pe ant tak jao, phir backtrack. Connected components, cycle detection, tree traversals.
• Rule: Graphs aur 2D grids me hamesha visited state track karo, infinite loop se bachne ke liye.

Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{startR, startC});
boolean[][] visited = new boolean[R][C];
visited[startR][startC] = true;

while (!q.isEmpty()) {
    int[] cur = q.poll();
    // 4 directions (up, down, left, right) explore karo:
    // cell valid aur unvisited ho to visited mark karke queue me push karo
}

9.10 Greedy

• Core idea: Har step pe locally best / safest choice lo, bina aage ka soche. Tab kaam karta hai jab local optimum hi global optimum banaye.
• Verification: Aksar data sort karne ke baad lagta hai. Apne logic pe counter-example dhoondo; na mile to greedy safe hai.

9.11 Heap (PriorityQueue)

• Core idea: Sabse chhota (min-heap) ya bada (max-heap) element O(1) me dekho, O(log n) me extract karo.
• Pro trick: "Top K largest" ke liye hamesha min-heap of size K maintain karo.

PriorityQueue<Integer> pq = new PriorityQueue<>();   // Java default = Min-Heap
for (int x : arr) {
    pq.add(x);
    if (pq.size() > k) {
        pq.poll();   // jo sabse chhota hai wo bahar
    }
}
// pq.peek() ab exact k-th largest element hai

Ye ladder aapko test case se optimal code tak systematically guide karta hai. 4 phases me structured hai:

Phase 1 — Problem breakdown

Phase 2 — Manual observation

Phase 3 — Optimization breakthrough

Phase 4 — Execution and verification

Prescription Matrix — waste ko tool se match karo

Final code submit karne se pehle ye 9 checks zaroor verify karo (tick lagao):

Dimag blank ho jaye ya code TLE de raha ho, to is diagnostic flow ko follow karo:

Situation-wise action plan

Har example me wahi Thinking Ladder laga hai: test case observation se shuru, clean Java code pe khatam.

13.1 Product of Array Except Self

Problem: Har index i ke liye baaki sab elements ka product nikalo. Division strictly disallowed hai.
Test case: nums = [1,2,3,4] → [24,12,8,6]

Dry run trace:

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];

    // Pass 1: Left prefix products
    int left = 1;
    for (int i = 0; i < n; i++) {
        ans[i] = left;
        left *= nums[i];
    }

    // Pass 2: Right suffix products multiply karo
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        ans[i] *= right;
        right *= nums[i];
    }
    return ans;
}

13.2 Subarray Sum Equals K

Problem: Kitne contiguous subarrays ka sum exactly k hai? (Negative numbers allowed.)
Test case: nums = [1,2,3], k = 3 → 2 (subarrays [1,2] aur [3])

Dry run trace:

public int subarraySum(int[] nums, int k) {
    int count = 0, prefix = 0;
    Map<Integer, Integer> seen = new HashMap<>();
    seen.put(0, 1);                      // base: empty prefix sum is 0

    for (int x : nums) {
        prefix += x;
        count += seen.getOrDefault(prefix - k, 0);
        seen.put(prefix, seen.getOrDefault(prefix, 0) + 1);
    }
    return count;
}

13.3 Container With Most Water

Problem: Non-negative heights di gayi hain. Do vertical lines chuno jisse beech me sabse zyada paani hold ho.
Test case: height = [1,8,6,2,5,4,8,3,7] → 49

Dry run trace:

public int maxArea(int[] h) {
    int l = 0, r = h.length - 1, best = 0;

    while (l < r) {
        int currentArea = (r - l) * Math.min(h[l], h[r]);
        best = Math.max(best, currentArea);

        // hamesha chhoti height wali line ko move karo
        if (h[l] < h[r]) {
            l++;
        } else {
            r--;
        }
    }
    return best;
}

13.4 Merge Intervals

Problem: Overlapping intervals ki list ko merge karke non-overlapping intervals banao.
Test case: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]

public int[][] merge(int[][] intervals) {
    // 1. Start point ke hisaab se sort karo
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    List<int[]> res = new ArrayList<>();
    res.add(intervals[0]);

    for (int i = 1; i < intervals.length; i++) {
        int[] last = res.get(res.size() - 1);

        // current interval pichhle se overlap karta hai?
        if (intervals[i][0] <= last[1]) {
            last[1] = Math.max(last[1], intervals[i][1]);         // merge end
        } else {
            res.add(intervals[i]);                                // naya interval
        }
    }
    return res.toArray(new int[res.size()][]);
}

13.5 Koko Eating Bananas

Problem: Piles me bananas hain. Koko 1 ghante me kisi pile se k bananas kha sakti hai. h ghante ke andar sab khatam karne ke liye minimum speed k kya ho?
Test case: piles = [3,6,7,11], h = 8 → 4

Dry run trace:

public int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (hours(piles, mid) <= h) {
            hi = mid;      // mid feasible hai, aur chhota try karo
        } else {
            lo = mid + 1; // mid too slow hai, speed badhao
        }
    }
    return lo;
}

private long hours(int[] piles, int k) {
    long total = 0;
    for (int p : piles) {
        total += (p + k - 1) / k;   // integer math for ceil(p / k)
    }
    return total;
}

13.6 Coin Change (DP kaise banta hai)

Problem: Coins ke denominations diye hain. Given amount banane ke liye minimum kitne coins lagenge?
Test case: coins = [1,2,5], amount = 11 → 3 (5 + 5 + 1)

Dry run trace:

public int coinChange(int[] coins, int amount) {
    int INF = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;                              // base: 0 amount needs 0 coins

    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (a - c >= 0) {
                dp[a] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}

13.7 Number of Islands (Grid + DFS)

Problem: 2D grid me '1' = zameen, '0' = paani. Connected zameen (horizontal / vertical) milkar ek island banati hai. Total islands count karo.
Test case: Grid: 1100 / 1100 / 0010 / 0001 → 3 islands

public int numIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {
                count++;
                dfs(grid, r, c);        // poore island ko '0' bana do
            }
        }
    }
    return count;
}

private void dfs(char[][] g, int r, int c) {
    // Boundary check + water check
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') {
        return;
    }
    g[r][c] = '0';                      // mark visited
    dfs(g, r + 1, c);                   // down
    dfs(g, r - 1, c);                   // up
    dfs(g, r, c + 1);                   // right
    dfs(g, r, c - 1);                   // left
}

13.8 Subsets (Backtracking)

Problem: Array ke saare possible unique subsets (power set) return karo.
Test case: [1,2,3] → [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] (total 8)

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    go(nums, 0, new ArrayList<>(), res);
    return res;
}

private void go(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));      // har intermediate node ek valid subset

    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);               // 1. Choose
        go(nums, i + 1, path, res);      // 2. Explore
        path.remove(path.size() - 1);    // 3. Undo (backtrack)
    }
}

Sahi tareeka (high retention)

Recommended problems (Thinking Ladder apply karo)

Har problem pe ye 10 sawal poochho:

5 core mantras

Ek nazar me: n → complexity

A4 printout ya notebook me solve karne ke liye template. Is worksheet ko print karke har tough problem pe manually bharo.