250. Number of Longest Increasing Subsequence

🔗 LeetCode Problem: 673. Number of Longest Increasing Subsequence
📊 Difficulty: Medium
🏷️ Topics: Array, Dynamic Programming, Binary Indexed Tree, Segment Tree, DP - LIS

Problem Statement

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Constraints: - 1 <= nums.length <= 2000 - -10^6 <= nums[i] <= 10^6

---

🧒 Let's Build Understanding from Absolute Scratch

What Does This Problem REALLY Ask?

Let me start with something I already know: Problem 247 (LIS)

PROBLEM 247: Longest Increasing Subsequence
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Input: nums = [1, 3, 5, 4, 7]

Question: What's the LENGTH of the longest increasing subsequence?

Let me find all increasing subsequences:
  [1] → length 1
  [3] → length 1
  [5] → length 1
  [4] → length 1
  [7] → length 1
  [1, 3] → length 2
  [1, 5] → length 2
  [1, 4] → length 2
  [1, 7] → length 2
  [3, 5] → length 2
  [3, 4] → length 2
  [3, 7] → length 2
  [5, 7] → length 2
  [4, 7] → length 2
  [1, 3, 5] → length 3
  [1, 3, 4] → length 3
  [1, 3, 7] → length 3
  [1, 5, 7] → length 3
  [1, 4, 7] → length 3
  [3, 5, 7] → length 3
  [3, 4, 7] → length 3
  [1, 3, 5, 7] → length 4 ← This one!
  [1, 3, 4, 7] → length 4 ← And this one!

Maximum length: 4
Answer for Problem 247: 4 ✓

PROBLEM 250: Number of LIS (THIS PROBLEM!)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Same input: nums = [1, 3, 5, 4, 7]

Question: HOW MANY subsequences have the longest length?

From above, longest length = 4
How many have length 4?
  [1, 3, 5, 7] → length 4 ✓
  [1, 3, 4, 7] → length 4 ✓

Count: 2 subsequences! ✓
Answer for Problem 250: 2 ✓

KEY DIFFERENCE:
  Problem 247: Return LENGTH (just a number)
  Problem 250: Return COUNT of sequences with that length! 🔑

Building Understanding With Simple Example

Let me work through: nums = [1, 2, 3]

Find all increasing subsequences:
  [1] → length 1
  [2] → length 1
  [3] → length 1
  [1, 2] → length 2
  [1, 3] → length 2
  [2, 3] → length 2
  [1, 2, 3] → length 3 ← Longest!

Maximum length: 3
Subsequences with length 3: Just [1, 2, 3]
Count: 1 ✓

Another example: nums = [1, 2, 2]

Wait! Let me be careful with indices!

  Index:  0  1  2
  Value:  1  2  2

Subsequences:
  [1] (index 0) → length 1
  [2] (index 1) → length 1
  [2] (index 2) → length 1
  [1, 2] (indices 0,1) → length 2 ← Longest!
  [1, 2] (indices 0,2) → length 2 ← Also longest!
  [2, 2]? NO! Not strictly increasing! ✗

Maximum length: 2
Subsequences with length 2: 
  [1, 2] using index 1
  [1, 2] using index 2

Count: 2 different subsequences! ✓

IMPORTANT: Even if values are same, different indices make
           them DIFFERENT subsequences! 🔑

What Information Do I Need To Track?

From Problem 247, I learned:
  dp[i] = length of LIS ending at position i

Example: nums = [1, 3, 5, 4, 7]

From Problem 247:
  dp[0] = 1 (just [1])
  dp[1] = 2 (can be [1,3])
  dp[2] = 3 (can be [1,3,5])
  dp[3] = 3 (can be [1,3,4])
  dp[4] = 4 (can be [1,3,5,7] or [1,3,4,7])

Maximum: 4

But for THIS problem, I need MORE information!

At position 4 (value 7):
  dp[4] = 4
  But HOW MANY ways can I make length 4 ending at 7?

  I can extend from position 2 (value 5):
    Sequences ending at 5 with length 3: How many?

  I can extend from position 3 (value 4):
    Sequences ending at 4 with length 3: How many?

I need to track COUNT too! 🔑

NEW IDEA:
  dp[i] = length of LIS ending at i (same as before)
  count[i] = NUMBER of LIS ending at i with that length! ← NEW!

This is what I need! ✓

---

🤔 Building Intuition - The Counting Logic

Understanding Count Array - Simple Example

Let's work through: nums = [1, 2, 3]

I'll track TWO arrays:
  dp[i] = length of LIS ending at i
  count[i] = number of such sequences

Initialize:
  dp = [1, 1, 1] (each element alone)
  count = [1, 1, 1] (one way to make each)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS INDEX 0 (value 1):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

No previous elements.
dp[0] = 1 (just [1])
count[0] = 1 (one way: [1])

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS INDEX 1 (value 2):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Check previous positions:

j=0 (value 1):
  2 > 1? YES! Can extend!

  If I extend from j=0:
    New length = dp[0] + 1 = 1 + 1 = 2

  Current state at i=1:
    dp[1] = 1

  New length (2) > current (1)?
    YES! Found LONGER sequence!

    Update:
      dp[1] = 2
      count[1] = count[0] = 1
      (I inherit the count from where I extend!)

  Why count[1] = count[0]?
    Because: Every sequence ending at 0 can be extended to 1!
    Sequences ending at 0: 1 way ([1])
    Extending with 2: [1,2]
    So: 1 way ending at 1! ✓

State:
  dp = [1, 2, 1]
  count = [1, 1, 1]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS INDEX 2 (value 3):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Check previous positions:

j=0 (value 1):
  3 > 1? YES!
  New length = dp[0] + 1 = 2
  Current: dp[2] = 1
  2 > 1? YES! Update!
    dp[2] = 2
    count[2] = count[0] = 1

j=1 (value 2):
  3 > 2? YES!
  New length = dp[1] + 1 = 2 + 1 = 3
  Current: dp[2] = 2
  3 > 2? YES! Found EVEN LONGER!
    dp[2] = 3
    count[2] = count[1] = 1

Final state:
  dp = [1, 2, 3]
  count = [1, 1, 1]

Maximum length: 3
How many with length 3? 
  Check all positions where dp[i] = 3:
    Position 2: count[2] = 1

Total: 1 ✓

The sequence: [1, 2, 3] ✓

Understanding When Counts Add Up

Here's the KEY insight for counting:

When processing position i, checking position j:

CASE 1: New length > current length
  Found LONGER sequence!
  RESET the count!
  count[i] = count[j]

CASE 2: New length == current length
  Found ANOTHER way to make SAME length!
  ADD to the count!
  count[i] += count[j]

CASE 3: New length < current length
  This doesn't help!
  Don't update anything!

Example showing CASE 2:

nums = [1, 3, 5, 4, 7]

When processing i=4 (value 7):

  Check j=2 (value 5):
    7 > 5? YES!
    New length = dp[2] + 1 = 3 + 1 = 4
    Current: dp[4] = 1
    4 > 1? YES! (CASE 1)
      dp[4] = 4
      count[4] = count[2] = 1

  Check j=3 (value 4):
    7 > 4? YES!
    New length = dp[3] + 1 = 3 + 1 = 4
    Current: dp[4] = 4
    4 == 4? YES! (CASE 2) ← Different!
      count[4] += count[3]
      count[4] = 1 + 1 = 2

Final: count[4] = 2

Why? Because I can reach 7 with length 4 in TWO ways:
  1. Extend from position 2: [1,3,5] → [1,3,5,7]
  2. Extend from position 3: [1,3,4] → [1,3,4,7]

Both give length 4, so I ADD the counts! 🔑

Complete Medium Example - Step By Step

nums = [1, 3, 5, 4, 7]
indices: 0  1  2  3  4

Initialize:
  dp = [1, 1, 1, 1, 1]
  count = [1, 1, 1, 1, 1]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 0 (value 1):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

No previous elements.
dp[0] = 1, count[0] = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 1 (value 3):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

j=0 (value 1):
  3 > 1? YES!
  New length: dp[0] + 1 = 2
  Current: dp[1] = 1
  2 > 1? YES! (CASE 1)
    dp[1] = 2
    count[1] = count[0] = 1

Result: dp[1]=2, count[1]=1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 2 (value 5):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

j=0 (value 1):
  5 > 1? YES!
  New length: 2
  Current: 1
  2 > 1? YES! (CASE 1)
    dp[2] = 2
    count[2] = 1

j=1 (value 3):
  5 > 3? YES!
  New length: dp[1] + 1 = 2 + 1 = 3
  Current: dp[2] = 2
  3 > 2? YES! (CASE 1)
    dp[2] = 3
    count[2] = count[1] = 1

Result: dp[2]=3, count[2]=1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 3 (value 4):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

j=0 (value 1):
  4 > 1? YES!
  New length: 2
  Current: 1
  2 > 1? YES! (CASE 1)
    dp[3] = 2
    count[3] = 1

j=1 (value 3):
  4 > 3? YES!
  New length: 3
  Current: 2
  3 > 2? YES! (CASE 1)
    dp[3] = 3
    count[3] = count[1] = 1

j=2 (value 5):
  4 > 5? NO! Skip!

Result: dp[3]=3, count[3]=1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 4 (value 7):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

j=0 (value 1):
  7 > 1? YES!
  New length: 2
  Current: 1
  2 > 1? YES! (CASE 1)
    dp[4] = 2
    count[4] = 1

j=1 (value 3):
  7 > 3? YES!
  New length: 3
  Current: 2
  3 > 2? YES! (CASE 1)
    dp[4] = 3
    count[4] = 1

j=2 (value 5):
  7 > 5? YES!
  New length: dp[2] + 1 = 3 + 1 = 4
  Current: dp[4] = 3
  4 > 3? YES! (CASE 1)
    dp[4] = 4
    count[4] = count[2] = 1

j=3 (value 4):
  7 > 4? YES!
  New length: dp[3] + 1 = 3 + 1 = 4
  Current: dp[4] = 4
  4 == 4? YES! (CASE 2) ← KEY MOMENT!
    count[4] += count[3]
    count[4] = 1 + 1 = 2

Result: dp[4]=4, count[4]=2

Final arrays:
  dp = [1, 2, 3, 3, 4]
  count = [1, 1, 1, 1, 2]

Maximum length: max(dp) = 4

Count of sequences with length 4:
  Only position 4 has dp[4]=4
  count[4] = 2

Answer: 2 ✓

The two sequences:
  1. [1, 3, 5, 7] (extending from position 2)
  2. [1, 3, 4, 7] (extending from position 3)

The "Aha!" Moment - Why We Add Counts

Think about it like PATHS in a tree:

Position 0 (value 1):
  1 path: [1]

Position 1 (value 3):
  Extends from 0
  Inherits 1 path: [1] → [1,3]
  Total: 1 path

Position 2 (value 5):
  Extends from 1
  Inherits 1 path: [1,3] → [1,3,5]
  Total: 1 path

Position 3 (value 4):
  Extends from 1 (SAME source as position 2!)
  Inherits 1 path: [1,3] → [1,3,4]
  Total: 1 path

Position 4 (value 7):
  Can extend from BOTH 2 and 3!
  From position 2: 1 path [1,3,5] → [1,3,5,7]
  From position 3: 1 path [1,3,4] → [1,3,4,7]

  Both give SAME length (4)!
  So we ADD: 1 + 1 = 2 paths! ✓

Visual tree:
              [1]
               |
              [1,3]
             /     \
      [1,3,5]       [1,3,4]
           \         /
            [1,3,5,7]  [1,3,4,7]

Two different paths to length 4! 🔑

---

🔴 Approach 1: Brute Force - Generate All Sequences

The Naive Idea

Simplest approach:
  1. Generate ALL increasing subsequences
  2. Find the maximum length
  3. Count how many have that length

For nums = [1, 3, 5]:

  Subsequences:
    [1] → length 1
    [3] → length 1
    [5] → length 1
    [1,3] → length 2
    [1,5] → length 2
    [3,5] → length 2
    [1,3,5] → length 3 ← Max!

  Maximum: 3
  Count: 1 ✓

But how to generate all?

Using Recursion To Generate

For each element, we have TWO choices:
  1. SKIP it (don't include in current subsequence)
  2. TAKE it (if it's larger than previous)

This creates a recursion tree!

Example: nums = [1, 3, 5]

                    Start
                   /    \
             Skip 1      Take 1
              /  \        /   \
          Skip3 Take3  Skip3  Take3(>1)
          /  \   / \    / \    /  \
        ...  ...  ...  ...  ... [1,3,5]

Each path represents a subsequence!
We explore ALL paths! ✓

Complete Implementation

class Solution {
    private List<List<Integer>> allSequences;

    public int findNumberOfLIS(int[] nums) {
        allSequences = new ArrayList<>();

        // Generate all increasing subsequences
        generateAll(nums, 0, new ArrayList<>());

        // Find maximum length
        int maxLen = 0;
        for (List<Integer> seq : allSequences) {
            maxLen = Math.max(maxLen, seq.size());
        }

        // Count sequences with maximum length
        int count = 0;
        for (List<Integer> seq : allSequences) {
            if (seq.size() == maxLen) {
                count++;
            }
        }

        return count;
    }

    private void generateAll(int[] nums, int index, List<Integer> current) {
        // Base case: processed all elements
        if (index == nums.length) {
            // Store a copy of current subsequence
            allSequences.add(new ArrayList<>(current));
            return;
        }

        // Choice 1: Skip current element
        generateAll(nums, index + 1, current);

        // Choice 2: Take current element (if valid)
        boolean canTake = current.isEmpty() || 
                          nums[index] > current.get(current.size() - 1);

        if (canTake) {
            current.add(nums[index]);
            generateAll(nums, index + 1, current);
            current.remove(current.size() - 1); // Backtrack!
        }
    }
}

Understanding The Backtracking

What is backtracking?

When we add element to current:
  current.add(nums[index])
  ... explore with this element ...
  current.remove() ← Remove it back!

Why?
  Because current is SHARED across all recursive calls!
  We need to "undo" our choice before trying next option!

Example trace for [1, 3]:

generateAll(nums, 0, [])
  Skip 1:
    generateAll(nums, 1, [])
      Skip 3:
        generateAll(nums, 2, [])
          Base case: store []
      Take 3:
        current = [3]
        generateAll(nums, 2, [3])
          Base case: store [3]
        current.remove() → current = []

  Take 1:
    current = [1]
    generateAll(nums, 1, [1])
      Skip 3:
        generateAll(nums, 2, [1])
          Base case: store [1]
      Take 3:
        current = [1, 3]
        generateAll(nums, 2, [1, 3])
          Base case: store [1, 3]
        current.remove() → current = [1]
    current.remove() → current = []

All sequences: [], [3], [1], [1, 3]
Maximum length: 2
Count: 1 ([1, 3])

Why This Is Too Slow

TIME COMPLEXITY:

For each element: 2 choices (skip or take)
Total elements: n
Total subsequences: 2^n

Then we:
  - Find max length: O(2^n)
  - Count matching: O(2^n)

Total: O(2^n) ❌

For n = 20:
  2^20 = 1,048,576 subsequences! ❌

For n = 2000 (max constraint):
  2^2000 = IMPOSSIBLE! ❌

SPACE COMPLEXITY:
  Storing all subsequences: O(2^n × n)
  Recursion stack: O(n)

Verdict: Works for tiny inputs (n ≤ 20), FAILS for real inputs! ❌

---

🟢 Approach 2: Dynamic Programming (Optimal Solution)

The DP Idea

Instead of generating all sequences:
  Track information AS we build!

Two arrays:
  dp[i] = length of LIS ending at index i
  count[i] = number of LIS ending at index i

For each position i:
  Check all j < i
  If nums[i] > nums[j]: can extend!

    New length = dp[j] + 1

    If new length > current:
      Found longer! Reset count!
      dp[i] = new length
      count[i] = count[j]

    Else if new length == current:
      Found another way! Add count!
      count[i] += count[j]

Finally:
  Find maximum in dp[]
  Sum all count[i] where dp[i] == maximum

This is O(n²)! Much better! 🚀

Complete Implementation

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;

        // dp[i] = length of LIS ending at index i
        int[] dp = new int[n];

        // count[i] = number of LIS ending at index i
        int[] count = new int[n];

        // Initialize: each element alone is length 1
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);

        // Fill DP arrays
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // Can we extend from j to i?
                if (nums[i] > nums[j]) {
                    int newLen = dp[j] + 1;

                    if (newLen > dp[i]) {
                        // Found longer sequence!
                        dp[i] = newLen;
                        count[i] = count[j]; // Inherit count
                    } else if (newLen == dp[i]) {
                        // Found another way to make same length!
                        count[i] += count[j]; // Add count
                    }
                }
            }
        }

        // Find maximum length
        int maxLen = 0;
        for (int len : dp) {
            maxLen = Math.max(maxLen, len);
        }

        // Count sequences with maximum length
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen) {
                result += count[i];
            }
        }

        return result;
    }
}

Another Complete Example

nums = [2, 2, 2, 2, 2]

Initialize:
  dp = [1, 1, 1, 1, 1]
  count = [1, 1, 1, 1, 1]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 0: value 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

No previous elements.
dp[0] = 1, count[0] = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 1: value 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

j=0 (value 2):
  2 > 2? NO! Can't extend!

No updates!
dp[1] = 1, count[1] = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 2: value 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

j=0: 2 > 2? NO!
j=1: 2 > 2? NO!

No updates!
dp[2] = 1, count[2] = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 3: value 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

All previous values are 2, can't extend!
dp[3] = 1, count[3] = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 4: value 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

All previous values are 2, can't extend!
dp[4] = 1, count[4] = 1

Final arrays:
  dp = [1, 1, 1, 1, 1]
  count = [1, 1, 1, 1, 1]

Maximum length: 1

Positions with length 1: ALL of them!
  count[0] + count[1] + count[2] + count[3] + count[4]
  = 1 + 1 + 1 + 1 + 1
  = 5 ✓

Answer: 5

Why? Because each element alone is a valid subsequence!
  [2] at index 0
  [2] at index 1
  [2] at index 2
  [2] at index 3
  [2] at index 4

Five different subsequences, all with length 1! ✓

---

🔍 More Complex Example

Example: nums = [1, 2, 4, 3, 5, 4, 7, 2]

This has multiple LIS paths! Let me trace completely:

Initialize:
  dp = [1, 1, 1, 1, 1, 1, 1, 1]
  count = [1, 1, 1, 1, 1, 1, 1, 1]

Index 0 (value 1): dp[0]=1, count[0]=1

Index 1 (value 2):
  j=0 (1): 2>1 ✓ → dp[1]=2, count[1]=1

Index 2 (value 4):
  j=0 (1): 4>1 ✓ → dp[2]=2, count[2]=1
  j=1 (2): 4>2 ✓ → newLen=3 > 2 → dp[2]=3, count[2]=1

Index 3 (value 3):
  j=0 (1): 3>1 ✓ → dp[3]=2, count[3]=1
  j=1 (2): 3>2 ✓ → newLen=3 > 2 → dp[3]=3, count[3]=1
  j=2 (4): 3>4? NO

Index 4 (value 5):
  j=0 (1): 5>1 ✓ → dp[4]=2, count[4]=1
  j=1 (2): 5>2 ✓ → newLen=3 > 2 → dp[4]=3, count[4]=1
  j=2 (4): 5>4 ✓ → newLen=4 > 3 → dp[4]=4, count[4]=1
  j=3 (3): 5>3 ✓ → newLen=4 == 4 → count[4]+=1=2! ← KEY!

After index 4:
  dp[4]=4, count[4]=2

  Why 2? Two ways to reach length 4:
    Path 1: extend from index 2 → [1,2,4,5]
    Path 2: extend from index 3 → [1,2,3,5]

Index 5 (value 4):
  j=0: 4>1 ✓ → dp[5]=2, count[5]=1
  j=1: 4>2 ✓ → newLen=3 > 2 → dp[5]=3, count[5]=1
  j=2: 4>4? NO
  j=3: 4>3 ✓ → newLen=4 > 3 → dp[5]=4, count[5]=1
  j=4: 4>5? NO

Index 6 (value 7):
  j=0: 7>1 ✓ → dp[6]=2, count[6]=1
  j=1: 7>2 ✓ → newLen=3 > 2 → dp[6]=3, count[6]=1
  j=2: 7>4 ✓ → newLen=4 > 3 → dp[6]=4, count[6]=1
  j=3: 7>3 ✓ → newLen=4 == 4 → count[6]+=1=2
  j=4: 7>5 ✓ → newLen=5 > 4 → dp[6]=5, count[6]=2! ← Inherited!
  j=5: 7>4 ✓ → newLen=5 == 5 → count[6]+=1=3!

After index 6:
  dp[6]=5, count[6]=3

  Three ways to reach length 5:
    From j=4 (which has 2 ways): [1,2,4,5] and [1,2,3,5] → both extend to 7
    From j=5 (which has 1 way): [1,2,3,4] → extends to 7

  Total: 2 + 1 = 3 ways! ✓

Index 7 (value 2):
  Can't extend anything (2 is too small)
  dp[7]=1, count[7]=1

Final arrays:
  dp = [1, 2, 3, 3, 4, 4, 5, 1]
  count = [1, 1, 1, 1, 2, 1, 3, 1]

Maximum length: 5 (at index 6)
Count: 3 ✓

The three sequences:
  1. [1, 2, 4, 5, 7]
  2. [1, 2, 3, 5, 7]
  3. [1, 2, 3, 4, 7]

---

📊 Complexity Analysis

Time Complexity

Approach 1 - Brute Force:
  Generate all subsequences: O(2^n)
  Too slow! ❌

Approach 2 - DP:
  Outer loop: n iterations (i from 0 to n-1)
  Inner loop: up to n iterations (j from 0 to i-1)
  Each operation: O(1)

  Total: O(n²) ✓

For n = 2000:
  2000² = 4,000,000 operations
  Very fast! ✓

Space Complexity

Approach 1:
  Storing all sequences: O(2^n × n)
  Recursion stack: O(n)
  Total: O(2^n × n) ❌

Approach 2:
  Two arrays (dp, count): O(n) each
  Total: O(n) ✓

Much better! ✓

---

💻 Complete Working Code

class Solution {
  public int findNumberOfLIS(int[] nums) {
    int n = nums.length;

    // dp[i] = length of LIS ending at index i
    int[] dp = new int[n];

    // count[i] = number of LIS ending at index i with that length
    int[] count = new int[n];

    // Initialize: each element alone is length 1 with count 1
    Arrays.fill(dp, 1);
    Arrays.fill(count, 1);

    // Fill DP arrays
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < i; j++) {
        // Can we extend from j to i?
        if (nums[i] > nums[j]) {
          int newLen = dp[j] + 1;

          if (newLen > dp[i]) {
            // Found longer sequence - reset count
            dp[i] = newLen;
            count[i] = count[j];
          } else if (newLen == dp[i]) {
            // Found another way to make same length - add count
            count[i] += count[j];
          }
        }
      }
    }

    // Find maximum length
    int maxLen = 0;
    for (int len : dp) {
      maxLen = Math.max(maxLen, len);
    }

    // Sum counts for all positions with maximum length
    int result = 0;
    for (int i = 0; i < n; i++) {
      if (dp[i] == maxLen) {
        result += count[i];
      }
    }

    return result;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    System.out.println(sol.findNumberOfLIS(new int[] {1, 3, 5, 4, 7})); // 2
    System.out.println(sol.findNumberOfLIS(new int[] {2, 2, 2, 2, 2})); // 5
    System.out.println(sol.findNumberOfLIS(new int[] {1, 2, 4, 3, 5, 4, 7, 2})); // 3
  }
}

---

🔑 Key Insights Summary

The Learning Journey

CRAWL (Understanding):
  ✓ What's different from Problem 247? (count vs length)
  ✓ Understanding with simple examples
  ✓ Why we need TWO arrays (dp and count)
  ✓ Building intuition for counting

WALK (Building):
  ✓ When to RESET count (found longer)
  ✓ When to ADD count (found same length)
  ✓ Complete medium example traced
  ✓ Understanding the path tree concept

RUN (Mastery):
  ✓ Complete DP solution
  ✓ Complex example with multiple paths
  ✓ All three cases handled correctly
  ✓ True comprehensive understanding

Natural baby-to-expert progression! 🎯

The Core Understanding

1. WHY two arrays?
   dp[i] tracks LENGTH
   count[i] tracks HOW MANY ways!

2. WHAT are the three cases?
   newLen > current: RESET count (found longer!)
   newLen == current: ADD count (another way!)
   newLen < current: IGNORE (doesn't help!)

3. HOW do counts propagate?
   When extending from j to i:
     Inherit count[j]
     Because every path to j extends to i!

4. WHEN do we add?
   When MULTIPLE sources give SAME length!
   Each source contributes its count!

5. WHERE's the final answer?
   Find max length in dp[]
   Sum all count[i] where dp[i] == max! 🔑

Mental Model

Think of it as COUNTING PATHS:

Each position is a node.
Each extension is an edge.
Each path is a valid LIS.

When multiple paths reach same node with same length:
  COUNT them ALL! ✓

Example:
       [1]
        |
       [1,2]
      /    \
  [1,2,4]  [1,2,3]
      \    /
     [1,2,4,5] or [1,2,3,5]

Two paths to length 4!
count = 2 ✓

---

📝 Quick Revision

🎯 Core Concept

Problem 247: Return LENGTH of LIS
Problem 250: Return COUNT of LIS ← This one!
Need TWO arrays: dp[] and count[]

⚡ Algorithm

Initialize:
  dp[i] = 1 for all i
  count[i] = 1 for all i

For i from 1 to n-1:
  For j from 0 to i-1:
    if nums[i] > nums[j]:
      newLen = dp[j] + 1

      if newLen > dp[i]:
        dp[i] = newLen
        count[i] = count[j]  // Reset!

      else if newLen == dp[i]:
        count[i] += count[j]  // Add!

maxLen = max(dp)
result = sum of count[i] where dp[i] == maxLen

🔑 Quick Implementation

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
  public int findNumberOfLIS(int[] a) {
    // return recursive(a);
    return dp(a);
  }

  private int dp(int[] a) {
    int len = a.length;
    // step 1: initialize dp and count arrays
    // dp[i]: max len of any subsequence considering a[i]
    // will be [1, 2, 3, 3, 4] for [1, 3, 5, 4, 7]
    // will be [1, 1, 1, 1, 1] for [2, 2, 2, 2, 2]
    int[] dp = new int[len];
    Arrays.fill(dp, 1);
    // count[i]: count of such max len subsequences considering a[i]
    // will be [1, 1, 1, 1, 2] for [1, 3, 5, 4, 7]
    // will be [1, 1, 1, 1, 1] for [2, 2, 2, 2, 2]
    int[] count = new int[len];
    Arrays.fill(count, 1);

    // step 2: same as previous LIS except the count array part
    for (int i = 1; i < len; i++) {
      for (int j = 0; j < i; j++) {
        if (a[i] > a[j] && dp[i] < 1 + dp[j]) {
          dp[i] = 1 + dp[j];
          count[i] = count[j];
        } else if (a[i] > a[j] && dp[i] == 1 + dp[j]) {
          // step 3: this is the changing step to consider count
          count[i] = count[j] + count[i];
        }
      }
    }

    // step 3: find the max length subsequence
    int maxLen = dp[0];
    for (int i = 1; i < len; i++) {
      maxLen = Math.max(maxLen, dp[i]);
    }

    // step 4: count the result of max length sequences
    int res = 0;
    for (int i = 0; i < len; i++) {
      if (dp[i] == maxLen) {
        res = res + count[i];
      }
    }

    return res;
  }

  private int recursive(int[] a) {
    List<List<Integer>> subSequences = new ArrayList<>();
    // step 1: create all increasing subsequences
    recursiveUtil(a, 0, new ArrayList<>(), subSequences);

    // step 7: get max len of all increasing subsequences
    int maxSize = 0;
    for (List<Integer> s : subSequences) {
      maxSize = Math.max(maxSize, s.size());
    }

    // step 8: get the count of sequences having length maxSize
    int count = 0;
    for (List<Integer> s : subSequences) {
      if (s.size() == maxSize) {
        count++;
      }
    }

    return count;
  }

  private void recursiveUtil(int[] a, int i, ArrayList<Integer> curr, List<List<Integer>> subSequences) {
    // step 6: base case
    if (i == a.length) {
      subSequences.add(new ArrayList<>(curr));

      return;
    }

    // Step 2: skip the existing number at index and proceed to next index.
    recursiveUtil(a, i + 1, curr, subSequences);

    // step 3: take the existing number at index only if its greater than the
    // previous number of the current list.
    if (curr.size() == 0 || a[i] > curr.get(curr.size() - 1)) {
      // step 4: add to the current list and proceed to next
      curr.add(a[i]);
      recursiveUtil(a, i + 1, curr, subSequences);
      // step 5: remove from the current list and proceed to next as this is a
      // bracktracking process.
      curr.remove(curr.size() - 1);
    }
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.findNumberOfLIS(new int[] { 1, 3, 5, 4, 7 }) == 2);
    System.out.println(s.findNumberOfLIS(new int[] { 2, 2, 2, 2, 2 }) == 5);
  }
}

🎪 Memory Aid

"Length tracks longest"
"Count tracks how many"
"Reset when longer, add when same"
"Sum all maxes for final answer"

Complexity: O(n²) time, O(n) space

---

🎉 Congratulations!

You've mastered through baby steps: - ✅ CRAWL: Understanding counting vs length - ✅ WALK: Building the counting logic - ✅ RUN: Complete DP solution with counting - ✅ THREE cases for count updates - ✅ Multiple complex examples traced - ✅ Path tree visualization - ✅ Complete working code - ✅ True comprehensive understanding

You've learned the COUNTING variant of LIS with true textbook-style baby-to-expert learning! 🚀✨

KEY TAKEAWAY: When problem asks "how many" instead of "how long", track BOTH length AND count! Each position can have multiple ways to achieve its length! 🔑