🧠 🚀Array-Algorithms-Mastery (DIAGRAM STYLE)

ARRAY / STRING PROBLEMS
│
├── 🔹 SUBARRAY (Continuous)
│   │
│   ├── Prefix Sum
│   │     P[i] = P[i-1] + arr[i]
│   │
│   ├── Sliding Window
│   │     Expand → Shrink
│   │
│   ├── Kadane’s Algorithm
│   │     Max subarray sum
│   │
│   ├── HashMap + Prefix
│   │     prefix_sum - K
│   │
│   └── Contribution Technique
│         (i+1)(n-i)
│
│
├── 🔹 SUBSEQUENCE (Not Continuous)
│   │
│   ├── Recursion Tree (Take / Not Take)
│   │
│   ├── Total = 2^N
│   │
│   ├── Types:
│   │     ├── Generate All
│   │     ├── Sum = K
│   │     ├── Count
│   │     ├── Print One
│   │     ├── Max / Min
│   │
│   ├── Bitmask (Binary Method)
│   │
│   └── DP (Optimization)
│
│
├── 🔹 TWO POINTER
│   │
│   ├── Sorted Array
│   ├── Pair Sum
│   └── Reduce O(N²) → O(N)
│
│
└── 🔹 BACKTRACKING / DP
    │
    ├── Recursion Tree
    ├── Overlapping Subproblems
    ├── Memoization / Tabulation
    │
    ├── LIS
    └── LCS

🧠 CORE MATHEMATICAL IDEAS (VISUAL)

🌳 MASTER DIAGRAM: SUBSET / ARRAY-BASED PROBLEMS

                         ARRAY PROBLEMS
                                │
                ┌───────────────┴────────────────┐
                │                                │
          SUBARRAY                         SUBSET / COMBINATION
       (continuous)                        (non-continuous)
                                                │
                      ┌─────────────────────────┼─────────────────────────┐
                      │                         │                         │
                 RECURSION                BACKTRACKING              DYNAMIC PROGRAMMING
                      │                         │                         │
                      │                         │                         │
              (decision tree)         (generate all solutions)     (optimize / store results)
                      │                         │                         │
                      └───────────────┬─────────┴─────────┬───────────────┘
                                      │                   │
                               SUBSET PROBLEMS        KNAPSACK FAMILY
                                      │                   │
         ┌────────────────────────────┼───────────────┐   │
         │                            │               │   │
   POWER SET                   SUBSET SUM      COMBINATION SUM   (Unbounded)
 (All subsets)              (target sum)         │
         │                            │           │
         │                            │           │
   2^n subsets                pick / not pick   reuse allowed
         │                            │           │
         │                            │           │
         │                            │           │
         ▼                            ▼           ▼

   ┌─────────────┐         ┌────────────────┐   ┌────────────────────┐
   │ Backtracking│         │  DP (0/1 Knapsack)│ │ Backtracking (DFS) │
   └─────────────┘         └────────────────┘   └────────────────────┘

                                      │
                                      ▼

                         PARTITION PROBLEMS
                                      │
                     ┌────────────────┴────────────────┐
                     │                                 │
            EQUAL PARTITION                MIN SUBSET DIFFERENCE
                     │                                 │
                     │                                 │
          subset sum = S/2              minimize |S - 2*S1|
                     │                                 │
                     ▼                                 ▼
            DP (0/1 Knapsack)                  DP + optimization

🔥 MATHEMATICAL LAYER (UNDER THE HOOD) Power Set: → 2^n combinations → binary decisions

Subset Sum: → a₁ + a₂ + ... = target

Equal Partition: → S1 = S2 = S/2

Min Difference: → minimize |S - 2*S1|

Combination Sum: → a₁x₁ + a₂x₂ + ... = target (x₁, x₂ ≥ 0)

🔥 DECISION FLOW (HOW TO IDENTIFY PROBLEM)

              GIVEN ARRAY PROBLEM
                      │
      ┌───────────────┴───────────────┐
      │                               │
 Is it continuous?              Not continuous?
      │                               │
  Subarray                     Subset Problems
                                      │
                  ┌───────────────────┼───────────────────┐
                  │                   │                   │
           Need ALL subsets?     Need TARGET SUM?   Reuse allowed?
                  │                   │                   │
           Backtracking         Subset Sum DP       Combination Sum
                  │                   │                   │
                  │                   │                   │
                  ▼                   ▼                   ▼
           Power Set         Equal Partition       Unbounded Knapsack
                             Min Difference

🔥 CORE ALGORITHM RELATION

Backtracking (DFS)
   │
   ├── Power Set
   ├── Combination Sum
   └── Subset Sum (basic)

Dynamic Programming
   │
   ├── Subset Sum
   ├── Equal Partition
   └── Min Subset Difference

Knapsack Family
   │
   ├── 0/1 Knapsack → Subset Sum
   └── Unbounded Knapsack → Combination Sum

🔷 🧠 Complete Topic Map

2D ARRAY
│
├── Basics
│   ├── Input/Output
│   ├── Row/Column traversal
│   ├── Diagonals
│
├── Operations
│   ├── Sum
│   ├── Addition
│   ├── Multiplication
│
├── Searching
│   ├── Linear Search
│   ├── Sorted Matrix Search
│
├── Graph on Grid
│   ├── BFS
│   ├── DFS
│   ├── Number of Islands
│
├── Backtracking
│   ├── Maze solving
│
├── Dynamic Programming
│   ├── Unique Paths
│
├── Prefix Sum
│   ├── 1D / 2D prefix
│
├── Transformations
│   ├── Transpose
│   ├── Rotation

🔷 📌 2D Array – Complete Summary 🔶 1. Basics Matrix = rows × columns Access → arr[i][j] Traversal → nested loops

🔶 2. Diagonals Primary → i == j Secondary → i + j = n - 1

🔶 3. Basic Operations Row sum Column sum Matrix addition Matrix multiplication

🔶 4. Searching ✔ Linear Search Check every element Time → O(n × m) ✔ Optimized (Sorted Matrix) Start top-right Move left / down Time → O(n + m)

🔶 5. BFS (Grid as Graph) Use queue Explore level by level Used in shortest path

🔶 6. DFS Use recursion Go deep → backtrack Used in connected components

🔶 7. Backtracking Try → fail → undo Used in: Maze Sudoku N-Queens

🔶 8. Dynamic Programming (DP) ✔ Unique Paths dp[i][j]=dp[i−1][j]+dp[i][j−1] Count paths in grid

🔶 9. Prefix Sum ✔ Idea Precompute sum ✔ Use Fast submatrix queries

🔶 10. Matrix Rotation 90° Clockwise → transpose + reverse rows 90° Anti → transpose + reverse columns 180° → reverse rows + reverse columns

🔶 11. Number of Islands DFS + connected components Count groups of '1' 🔷 🧠 Core Concepts Used Nested loops Recursion Graph traversal Dynamic programming Mathematical formulas 🔷 📊 Time Complexities Concept Time Traversal O(n × m) BFS / DFS O(n × m) Prefix Query O(1) DP Grid O(n × m)