Cosmic Module

D

Qubits of DPK

March 6, 2026

Core DSA

Core Principle

Scan once → maintain state → update answer
Everything in this pattern reduces to:
plain text
QUBITS OF DPK
1for each element
2    update state
3    update answer
No nested loops.

MENTAL MODELS (SUPER IMPORTANT)

1️⃣ Running State Model

Most problems maintain one evolving variable.
Examples:
General template:
plain text
QUBITS OF DPK
1state = initialValue
2
3for element in array:
4    update state
5    update answer

2️⃣ Reset Logic Model

Many traversal problems have a reset condition.
Example:
plain text
QUBITS OF DPK
1if sequence breaks → reset state
Examples:
Template:
plain text
QUBITS OF DPK
1if(condition continues)
2    state += value
3else
4    state = restartValue

3️⃣ Best-So-Far Model

Track best answer so far.
Examples:
Template:
plain text
QUBITS OF DPK
1answer = max(answer, state)

4️⃣ Prefix State Model

Instead of recomputing earlier values.
Maintain something about past elements.
Examples:
Template:
plain text
QUBITS OF DPK
1prefixState = update(prefixState, currentElement)

FORMULAS / TRANSFORMATIONS

These appear repeatedly in Pattern 1.

Kadane Formula

Used in:
  • Max Subarray
  • Circular Subarray
plain text
QUBITS OF DPK
1currentSum = max(nums[i], currentSum + nums[i])
2maxSum = max(maxSum, currentSum)

Stock Formula

Used in:
  • LC 121
plain text
QUBITS OF DPK
1minPrice = min(minPrice, price)
2
3profit = price - minPrice
4
5maxProfit = max(maxProfit, profit)

Greedy Increment Formula

Used in:
  • Stock II
  • Consecutive Gains
plain text
QUBITS OF DPK
1if(arr[i] > arr[i-1])
2    profit += arr[i] - arr[i-1]

Prefix / Suffix Trick

Used in:
  • Product Except Self
  • Sum of Beauties
plain text
QUBITS OF DPK
1prefix[i] = something before i
2suffix[i] = something after i
Then combine.

Expression Splitting Trick

Used in:
  • Sightseeing Pair
Original:
plain text
QUBITS OF DPK
1values[i] + values[j] + i - j
Rewrite:
plain text
QUBITS OF DPK
1(values[i] + i) + (values[j] - j)
Then maintain:
plain text
QUBITS OF DPK
1max(values[i] + i)

MICRO TRICKS INTERVIEWERS EXPECT

Trick 1 — Circular Array

plain text
QUBITS OF DPK
1(i + 1) % n
Used in:
  • Sorted Rotated Array

Trick 2 — Sentinel Values

For max tracking problems.
Example:
plain text
QUBITS OF DPK
1firstMax = Long.MIN_VALUE
Used in:
  • Third Maximum

Trick 3 — Avoid Extra Space

Many prefix arrays can become one variable.
Example:
Instead of:
plain text
QUBITS OF DPK
1prefixMax[]
Use:
plain text
QUBITS OF DPK
1maxSoFar

Trick 4 — One Pass Kadane Variation

Maintain two states simultaneously.
Example:
plain text
QUBITS OF DPK
1currentMax
2currentMin
Used in:
  • Maximum Product Subarray
  • Circular Subarray

COMMON INTERVIEW BUGS

These are very common mistakes.

Bug 1 — Wrong Reset

Example:
plain text
QUBITS OF DPK
1currSum = 0
Correct:
plain text
QUBITS OF DPK
1currSum = nums[i]

Bug 2 — Overwriting Answer

Wrong:
plain text
QUBITS OF DPK
1answer = value
Correct:
plain text
QUBITS OF DPK
1answer += value

Bug 3 — Missing Edge Cases

Always check:
plain text
QUBITS OF DPK
1n == 1
2all negatives
3all same

Bug 4 — Off-By-One Errors

Typical mistakes:
plain text
QUBITS OF DPK
1i < n-1
2i <= n-1
Always confirm.

INTERVIEW THOUGHT PROCESS

When you see a problem ask:

1️⃣ Can I solve in one pass?

If yes → Pattern 1.

2️⃣ What state do I maintain?

Examples:
plain text
QUBITS OF DPK
1min price
2current sum
3max score
4prefix product

3️⃣ When does the state reset?

Example:
plain text
QUBITS OF DPK
1sequence breaks
2pattern breaks
3sum becomes negative

4️⃣ When do I update the answer?

plain text
QUBITS OF DPK
1every step
2or after condition

GOLDEN INTERVIEW LINE

Say this when you recognize Pattern 1:
“This problem can be solved using a single traversal by maintaining running state variables and updating the answer incrementally.”
Interviewers love this sentence.

WHAT YOU BUILT WITH THESE 30 PROBLEMS

You now have mastery over:
plain text
QUBITS OF DPK
1running sums
2running counts
3running min/max
4prefix tracking
5greedy increments
6circular arrays
7expression transformation
This is the foundation of 40–50% of array interview questions.

FINAL INTUITION TEST

If I give you an array problem and say:
plain text
QUBITS OF DPK
1Find something maximum
2or track something
3or detect a pattern
Your brain should immediately think:
plain text
QUBITS OF DPK
1SCAN + STATE
That means Pattern 1 is fully internalized.

THE 10 CORE BRAIN PATTERNS (From Your 30 Problems)

1️⃣ Running Maximum / Minimum Tracker

Core Idea

Track the best element seen so far while scanning.

Template

plain text
QUBITS OF DPK
1best = initialValue
2
3for each element:
4    best = update(best, element)

Used In

  • Largest Element
  • Second Largest
  • Third Maximum
  • Stock Profit
  • Sightseeing Pair

Example

Stock I
plain text
QUBITS OF DPK
1minPrice = Math.min(minPrice, price)
2maxProfit = Math.max(maxProfit, price - minPrice)

Interview Signal

“I need the best value seen before this index.”

2️⃣ Running Sum / Count

Core Idea

Accumulate a value as we traverse.

Template

plain text
QUBITS OF DPK
1running += value

Used In

  • Running Sum
  • Consecutive Ones
  • Ascending Subarray Sum

Example

plain text
QUBITS OF DPK
1if(nums[i] == 1)
2    count++
3else
4    count = 0

Interview Signal

“I need to measure a streak.”

3️⃣ Reset on Break

Core Idea

If a condition fails → restart computation.

Template

plain text
QUBITS OF DPK
1if(condition continues)
2    state += value
3else
4    state = restart

Used In

  • Maximum Subarray
  • Ascending Subarray
  • Alternating Subarray
  • Mountain Array

Example

Kadane
plain text
QUBITS OF DPK
1currentSum = Math.max(nums[i], currentSum + nums[i])

Interview Signal

“The sequence breaks here.”

4️⃣ Best-So-Far Comparison

Core Idea

Every iteration checks if we improved the answer.

Template

plain text
QUBITS OF DPK
1answer = Math.max(answer, candidate)

Used In

  • Max Subarray
  • Stock Profit
  • Sightseeing Pair

Interview Signal

“This step might produce the best answer.”

5️⃣ Prefix Memory

Core Idea

Track something about all previous elements.

Template

plain text
QUBITS OF DPK
1prefixState = update(prefixState)

Used In

  • Stock I
  • Sightseeing Pair
  • Sum of Beauties

Example

plain text
QUBITS OF DPK
1maxLeft = max(maxLeft, nums[i])

Interview Signal

“The answer depends on previous elements.”

6️⃣ Prefix + Suffix Combination

Core Idea

Compute left and right contributions separately.

Used In

  • Product Except Self
  • Sum of Beauties
  • Circular Subarray

Template

plain text
QUBITS OF DPK
1prefix[i]
2suffix[i]
3combine(prefix, suffix)

Interview Signal

“Each index depends on both sides.”

7️⃣ Expression Splitting Trick

Core Idea

Rewrite formulas to separate left part and right part.

Used In

  • Sightseeing Pair
Original
plain text
QUBITS OF DPK
1values[i] + values[j] + i - j
Rewrite
plain text
QUBITS OF DPK
1(values[i] + i) + (values[j] - j)
Then maintain best left value.

Interview Signal

“Split the formula into two independent parts.”

8️⃣ Circular Array Thinking

Core Idea

The array behaves like a ring.

Trick

plain text
QUBITS OF DPK
1(i + 1) % n

Used In

  • Sorted Rotated Array
  • Circular Subarray

Interview Signal

“The end connects back to the start.”

9️⃣ Greedy Increment Strategy

Core Idea

Instead of finding full segments, accumulate small gains.

Used In

  • Stock II
Example
plain text
QUBITS OF DPK
1if(priceToday > priceYesterday)
2    profit += difference

Interview Signal

“Local profit contributes to global optimum.”

Multiple State Tracking

Core Idea

Track multiple evolving states simultaneously.

Used In

  • Maximum Product Subarray
  • Third Maximum
  • Circular Subarray
Example
plain text
QUBITS OF DPK
1currentMax
2currentMin
Why?
Negative numbers can flip sign.

Interview Signal

“One variable is not enough.”

THE REAL SECRET

Almost every Pattern-1 problem reduces to:
plain text
QUBITS OF DPK
1for each element:
2
3    update state
4
5    maybe reset state
6
7    update answer
That’s it.

Your Brain After 30 Problems

You should now instantly recognize:

Final Interview Sentence

When you see these problems say:
“This looks like a traversal problem where I maintain running state variables while scanning the array.”
That sentence alone signals strong DSA maturity.