DEV Community: Jayaprasanna Roddam

Math for Quantum Computing

Jayaprasanna Roddam — Sun, 22 Mar 2026 11:09:20 +0000

Linear Algebra Foundations for Quantum Computing (Explained Clearly)

1. Vector Spaces (Real vs Complex)

A vector space is a collection of objects (called vectors) where you can:

Add two vectors
Multiply a vector by a scalar

Real Vector Space

Scalars are real numbers (ℝ)
Example: ℝ² = (x, y)

Complex Vector Space

Scalars are complex numbers (ℂ)
Example: ℂ² = (a + ib, c + id)

Why Complex Matters in Quantum Computing

Quantum states use complex amplitudes
Phase (angle in complex plane) is crucial for interference

2. Basis

A basis is a set of vectors that:

Can generate every vector in the space (span)
Are linearly independent

Example (ℝ²)

Basis:

(1, 0)
(0, 1)

Any vector:
(x, y) = x(1,0) + y(0,1)

In Quantum Computing

Standard basis:

|0⟩ = (1, 0)
|1⟩ = (0, 1)

3. Dimension

The dimension of a vector space = number of vectors in a basis.

Examples

ℝ² → dimension = 2
ℝ³ → dimension = 3

In Quantum Computing

1 qubit → dimension = 2
n qubits → dimension = 2ⁿ

This exponential growth is where quantum power comes from.

4. Inner Product

The inner product measures similarity between two vectors.

Real Case

For vectors u = (u₁, u₂), v = (v₁, v₂):

⟨u, v⟩ = u₁v₁ + u₂v₂

Complex Case

⟨u, v⟩ = Σ (conjugate(uᵢ) * vᵢ)

Why It Matters

Gives length and angle
Used to compute probabilities in quantum mechanics

5. Norm

The norm is the length of a vector.

||v|| = √⟨v, v⟩

Example

v = (3, 4)

||v|| = √(3² + 4²) = 5

In Quantum Computing

Quantum states must be normalized:

||ψ|| = 1

Ensures probabilities sum to 1

6. Orthogonality

Two vectors are orthogonal if their inner product is zero:

⟨u, v⟩ = 0

Example

(1, 0) · (0, 1) = 0 → orthogonal

In Quantum Computing

|0⟩ and |1⟩ are orthogonal
Means they are perfectly distinguishable states

7. Eigenvalues & Eigenvectors

A vector v is an eigenvector of matrix A if:

A v = λ v

Where:

v = eigenvector
λ = eigenvalue

Intuition

Applying A:

Changes only the scale, not direction

Example

A = [[2, 0],

[0, 3]]

Eigenvectors:

(1, 0) → eigenvalue = 2
(0, 1) → eigenvalue = 3

Advanced Linear Algebra for Quantum Computing

1. Spectral Decomposition

Spectral decomposition expresses a matrix in terms of its eigenvalues and eigenvectors.

Definition

If a matrix A has eigenvalues λ₁, λ₂, ..., λₙ and corresponding orthonormal eigenvectors v₁, v₂, ..., vₙ:

A = Σ (λᵢ * |vᵢ⟩⟨vᵢ|)

Intuition

Any matrix can be “broken down” into simpler components
Each component scales along a specific direction (eigenvector)

Why It Matters in Quantum Computing

Measurement operators are decomposed this way
Helps compute probabilities of outcomes
Used heavily in quantum algorithms and physics

2. Unitary Matrices

A matrix U is unitary if:

U†U = UU† = I

Where:

U† = conjugate transpose of U
I = identity matrix

Key Properties

Preserves length (norm)
Reversible transformation
Columns are orthonormal

Intuition

Unitary transformations = rotation in complex space

In Quantum Computing

All quantum gates are unitary
Ensures:
- No information loss
- State remains normalized

Example

Hadamard Gate:

H = (1/√2) * [[1, 1],

[1, -1]]

3. Hermitian Operators

A matrix A is Hermitian if:

A† = A

Key Properties

Eigenvalues are real
Eigenvectors are orthogonal

Intuition

Hermitian matrices represent measurable quantities

In Quantum Computing

Observables (like position, energy) are Hermitian
Measurement outcomes = eigenvalues
System collapses to corresponding eigenvector

Example

A = [[2, i],

[-i, 3]]

This is Hermitian because A† = A

4. Tensor Products (VERY IMPORTANT)

Tensor product combines two vector spaces into a larger one.

Definition

If:
u = (a, b)

v = (c, d)

Then:

u ⊗ v = (ac, ad, bc, bd)

Example (Qubits)

|0⟩ = (1, 0)

|1⟩ = (0, 1)

Then:

|0⟩ ⊗ |1⟩ = |01⟩ = (0, 1, 0, 0)

Key Idea

1 qubit → 2D space
2 qubits → 4D space
n qubits → 2ⁿ space

Why Tensor Product is Critical

It enables:

Multi-qubit systems
Entanglement
Exponential state space growth

Important Insight

Not all states can be written as tensor products:

Example:

|ψ⟩ = (|00⟩ + |11⟩)/√2

This is entangled → cannot be separated

Why This Matters in Quantum Computing

Observables (like measurement) are operators
Eigenvalues = possible measurement results
Eigenvectors = corresponding states

Big Picture Connection

Vector spaces → where quantum states live
Basis → how we represent states
Inner product → gives probabilities
Norm → ensures valid quantum states
Orthogonality → distinguishes states
Eigen concepts → define measurement outcomes
Spectral decomposition → breaks operators into measurable parts
Unitary matrices → define valid quantum evolution
Hermitian operators → define measurements
Tensor products → scale systems exponentially

🧠 One Line Summary

Quantum computing =

Linear algebra over complex spaces + tensor products + unitary evolution

Quantum Computing

Jayaprasanna Roddam — Sun, 22 Mar 2026 11:05:50 +0000

1. Mathematical Foundations (Non-negotiable)

Linear Algebra

Vector spaces (real vs complex)
Basis, dimension
Inner product
Norms
Orthogonality
Eigenvalues & eigenvectors
Spectral decomposition
Unitary matrices
Hermitian operators
Tensor products (VERY IMPORTANT)

Probability Theory

Random variables
Conditional probability
Bayes theorem
Expectation & variance

Complex Numbers

Euler’s formula
Polar form
Complex conjugates

2. Quantum Mechanics Foundations

Postulates of Quantum Mechanics

State representation (wavefunction/state vector)
Measurement postulate
Evolution (Schrödinger equation intuition)
Observables as operators

Dirac Notation

Bra ⟨ψ| and Ket |ψ⟩
Inner product ⟨ψ|φ⟩
Outer product |ψ⟩⟨φ|

Quantum States

Pure states
Mixed states
Density matrices

3. Qubits and Multi-Qubit Systems

Single Qubit

Representation: α|0⟩ + β|1⟩
Normalisation condition
Measurement probabilities

Bloch Sphere

State as a point on a sphere
Rotations = quantum gates

Multi-Qubit Systems

Tensor product states
Basis states (|00⟩, |01⟩, etc.)
State explosion (2ⁿ-dimensional space)

Entanglement

Bell states
Non-separability
Difference from classical correlation

4. Quantum Gates

Single-Qubit Gates

Pauli Gates (X, Y, Z)
Hadamard (H)
Phase gate (S, T)

Multi-Qubit Gates

CNOT (controlled NOT)
Toffoli gate
Controlled-U gates

Properties

Unitary transformations
Reversibility

5. Quantum Circuits

Circuit Model

Wires = qubits
Gates = operations

Concepts

Circuit depth
Parallelism
Measurement at end

Universal Gate Sets

Gate completeness

6. Quantum Algorithms

Deutsch-Jozsa Algorithm

First demonstration of quantum advantage

Grover’s Algorithm

Unstructured search
Quadratic speedup

Shor’s Algorithm

Integer factorization
Cryptography implications

Quantum Fourier Transform (QFT)

Core subroutine for many algorithms

Variational Quantum Algorithms

VQE (Variational Quantum Eigensolver)
QAOA (Quantum Approximate Optimisation Algorithm)

7. Quantum Machine Learning (QML)

Data Encoding

Basis encoding
Amplitude encoding
Angle encoding

Quantum Models

Quantum Neural Networks (QNN)
Variational circuits
Quantum kernels

Hybrid Models

Classical + Quantum pipelines

Open Problems

Data loading bottleneck
Noise sensitivity
Lack of clear advantage

8. Quantum Hardware

Physical Implementations

Superconducting qubits
Trapped ions
Photonic systems

Challenges

Decoherence
Noise
Error rates

9. Quantum Error Correction

Bit flip error
Phase flip error
Shor code
Surface codes

10. Industry Landscape

IBM (Qiskit)
Google (Quantum AI, Sycamore)
Microsoft (Azure Quantum)
Rigetti Computing
IonQ

11. Limitations & Misconceptions

Not all problems get speedup
Quantum ≠ universally faster
Hardware still immature

12. Future Directions

Fault-tolerant quantum computing
Quantum internet
Quantum advantage in ML

13. Tools & Frameworks

Qiskit
Cirq
PennyLane

14. Research-Level Topics

Quantum complexity classes (BQP, NP)
Quantum supremacy vs advantage
Hamiltonian simulation
Adiabatic quantum computing

Sorting-based Pattern

Jayaprasanna Roddam — Fri, 09 Jan 2026 17:50:36 +0000

Sorting-based Pattern

OVERVIEW

The Sorting-based Pattern solves problems by first sorting the data and then
leveraging the sorted order to simplify logic, reduce complexity, or enable
other efficient patterns like two pointers or greedy decisions.

Sorting often transforms an otherwise complex problem into a structured one.

WHEN TO USE

Use this pattern when:

Order of elements matters
Relative comparisons are important
Grouping or pairing is required
You want to apply two pointers or greedy logic
A small increase in time (sorting) enables a big simplification

TIME & SPACE

Sorting Time : O(N log N)
Post-processing : Usually O(N)
Space Complexity : O(1) or O(N) depending on sort implementation

CORE IDEA

Sort the array first
Use the sorted property to:
- Eliminate unnecessary comparisons
- Make monotonic decisions
- Detect patterns easily
Apply linear scans or pointer-based techniques after sorting

EXAMPLE 1: Two Sum Using Sorting

Problem:
Check if there exists a pair with sum equal to target.

Logic:

Sort the array
Use two pointers from opposite ends

def two_sum_sort(nums, target):
nums.sort()
left = 0
right = len(nums) - 1

while left < right:
    s = nums[left] + nums[right]

    if s == target:
        return True
    elif s < target:
        left += 1
    else:
        right -= 1

return False

EXAMPLE 2: Merge Overlapping Intervals

Problem:
Given intervals, merge all overlapping intervals.

Logic:

Sort intervals by start time
Compare current interval with last merged interval

def merge_intervals(intervals):
if not intervals:
return []

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]

for start, end in intervals[1:]:
    last_end = merged[-1][1]

    if start <= last_end:
        merged[-1][1] = max(last_end, end)
    else:
        merged.append([start, end])

return merged

EXAMPLE 3: Find All Triplets That Sum to Zero (3Sum)

Problem:
Find all unique triplets such that a + b + c = 0.

Logic:

Sort array
Fix one element
Use two pointers for remaining two

def three_sum(nums):
nums.sort()
result = []

for i in range(len(nums)):
    if i > 0 and nums[i] == nums[i - 1]:
        continue

    left = i + 1
    right = len(nums) - 1

    while left < right:
        total = nums[i] + nums[left] + nums[right]

        if total == 0:
            result.append([nums[i], nums[left], nums[right]])

            left += 1
            right -= 1

            while left < right and nums[left] == nums[left - 1]:
                left += 1
            while left < right and nums[right] == nums[right + 1]:
                right -= 1

        elif total < 0:
            left += 1
        else:
            right -= 1

return result

EXAMPLE 4: Check if Array Can Be Made Non-decreasing

Problem:
Check if array can become non-decreasing by modifying at most one element.

Logic:

Sorting gives the target order
Compare with original array

def check_possibility(nums):
sorted_nums = sorted(nums)
mismatch = 0

for i in range(len(nums)):

    if nums[i] != sorted_nums[i]:

        mismatch += 1

        if mismatch > 2:

            return False

return True

IDENTIFICATION CHECKLIST

Ask these questions:

Does sorted order simplify decisions?
Can sorting unlock a linear scan?
Is relative ordering important?
Is N log N acceptable?

If yes, Sorting-based Pattern fits.

COMMON PITFALLS

Forgetting to handle duplicates after sorting
Assuming stable sort when it is not required
Sorting when order must be preserved
Overlooking faster non-sorting solutions

SUMMARY

Sort first, think later
Enables two pointers and greedy strategies
Often the key to reducing complexity
A must-know foundational problem-solving pattern

In-place Modification

Jayaprasanna Roddam — Fri, 09 Jan 2026 16:38:06 +0000

OVERVIEW

In-place Modification refers to solving problems by modifying the input data
structure directly, without using extra space proportional to input size.

The goal is to achieve:

O(1) auxiliary space
Optimal time complexity
Memory-efficient solutions

This pattern is very common in array problems and interview questions.

WHEN TO USE

Use in-place modification when:

The problem explicitly asks for in-place changes
Extra space is restricted
The final state of the array matters more than preserving the original
Elements can be safely overwritten or rearranged

TIME & SPACE

Time Complexity : Usually O(N)
Space Complexity : O(1)

CORE IDEA

Reuse the input array for writing results
Maintain one or more pointers to track write positions
Carefully avoid overwriting unprocessed data
Often combined with Two Pointers patterns

EXAMPLE 1: Remove Duplicates from Sorted Array

Problem:
Given a sorted array, remove duplicates in-place and return new length.

Logic:

One pointer reads elements
Another pointer writes unique values

def remove_duplicates(nums):
if not nums:
return 0

write = 1

for read in range(1, len(nums)):
    if nums[read] != nums[read - 1]:
        nums[write] = nums[read]
        write += 1

return write

EXAMPLE 2: Move Zeroes to End

Problem:
Move all zeroes to the end while maintaining relative order of non-zero elements.

Logic:

Write pointer tracks position for next non-zero
Read pointer scans array

def move_zeroes(nums):
write = 0

for read in range(len(nums)):
    if nums[read] != 0:
        nums[write], nums[read] = nums[read], nums[write]
        write += 1

return nums

EXAMPLE 3: Remove Element (Leetcode-style)

Problem:
Remove all occurrences of a given value in-place.

Logic:

Skip unwanted values
Overwrite them with valid ones

def remove_element(nums, val):
write = 0

for read in range(len(nums)):
    if nums[read] != val:
        nums[write] = nums[read]
        write += 1

return write

EXAMPLE 4: Reverse Array In-Place

Problem:
Reverse an array using constant space.

Logic:

Swap symmetric elements
Move inward

def reverse_array(nums):
left = 0
right = len(nums) - 1

while left < right:
    nums[left], nums[right] = nums[right], nums[left]
    left += 1
    right -= 1

return nums

EXAMPLE 5: Replace Elements with Greatest Element on Right Side

Problem:
Replace each element with the greatest element to its right.
Last element becomes -1.

Logic:

Traverse from right
Keep track of maximum so far

def replace_with_greatest(nums):
max_so_far = -1

for i in range(len(nums) - 1, -1, -1):

    current = nums[i]

    nums[i] = max_so_far

    max_so_far = max(max_so_far, current)

return nums

IDENTIFICATION CHECKLIST

Ask these questions:

Am I allowed to modify the input?
Can I reuse array slots safely?
Is extra space discouraged?
Can pointer-based overwriting solve this?

If yes, use In-place Modification.

COMMON PITFALLS

Overwriting values before they are processed
Forgetting write pointer increments
Assuming input order does not matter when it does
Using extra arrays unnecessarily

SUMMARY

Modify input directly
Constant extra space
Often paired with two pointers
Essential for space-optimized solutions

Hash Map Frequency Counting

Jayaprasanna Roddam — Fri, 09 Jan 2026 11:17:00 +0000

OVERVIEW

Hash Map Frequency Counting is a fundamental technique used to count occurrences
of elements while iterating through data.

Instead of repeatedly scanning the data, we store frequencies in a hash map
(dictionary) and update them in O(1) time per element.

This pattern is widely used in array, string, and prefix-sum based problems.

WHEN TO USE

Use this technique when:

You need counts of elements or characters
You are checking duplicates or uniqueness
You need fast lookups
The order of elements is not the primary concern

TIME & SPACE

Time Complexity : O(N)
Space Complexity : O(N)

CORE IDEA

Traverse the data once
Store element → frequency mapping
Update count as elements appear or disappear

Typical operations:

Increment frequency
Decrement frequency
Check presence or count

EXAMPLE 1: Count Frequency of Elements in an Array

def frequency_count(arr):
freq = {}

for element in arr:
    if element in freq:
        freq[element] += 1
    else:
        freq[element] = 1

return freq

EXAMPLE 2: Character Frequency in a String

def char_frequency(s):
freq = {}

for ch in s:
    freq[ch] = freq.get(ch, 0) + 1

return freq

EXAMPLE 3: Find First Non-Repeating Character

Problem:
Return the first character in a string that appears exactly once.

def first_non_repeating_char(s):
freq = {}

for ch in s:
    freq[ch] = freq.get(ch, 0) + 1

for ch in s:
    if freq[ch] == 1:
        return ch

return None

EXAMPLE 4: Subarray Sum Equals K (Using Prefix Sum + Hash Map)

Problem:
Count number of subarrays whose sum equals k.

Logic:

Use prefix sum
Store frequency of each prefix sum

def subarray_sum_equals_k(nums, k):
prefix_sum = 0
freq = {0: 1}
count = 0

for num in nums:
    prefix_sum += num

    if prefix_sum - k in freq:
        count += freq[prefix_sum - k]

    freq[prefix_sum] = freq.get(prefix_sum, 0) + 1

return count

EXAMPLE 5: Longest Substring with At Most K Distinct Characters

Problem:
Return length of longest substring containing at most k distinct characters.

def longest_substring_k_distinct(s, k):
left = 0
freq = {}
max_len = 0

for right in range(len(s)):

    freq[s[right]] = freq.get(s[right], 0) + 1

while len(freq) &gt; k:
    freq[s[left]] -= 1
    if freq[s[left]] == 0:
        del freq[s[left]]
    left += 1

max_len = max(max_len, right - left + 1)



return max_len

IDENTIFICATION CHECKLIST

Ask these questions:

Do I need to count occurrences?
Do I need fast existence checks?
Is repeated scanning too slow?
Can frequency changes track window validity?

If yes, Hash Map Frequency Counting is the right approach.

COMMON PITFALLS

Forgetting to delete zero-frequency keys
Using lists instead of hash maps for large ranges
Not initializing base cases (like prefix sum 0)
Overusing space when simple counters suffice

SUMMARY

Store element → count mapping
Enables O(1) updates and lookups
Essential for sliding window and prefix sum patterns
One of the most powerful everyday tools in problem solving

Difference Array

Jayaprasanna Roddam — Fri, 09 Jan 2026 11:05:43 +0000

OVERVIEW

Difference Array is an optimization technique used to efficiently perform
multiple range update operations on an array.

Instead of updating every element in a range [L, R], we update only the
boundaries and reconstruct the final array later using prefix sums.

This reduces range updates from O(N) to O(1).

WHEN TO USE

Use Difference Array when:

There are many range update operations
Final array is needed after all updates
Updates are additive (increment/decrement)
Queries are fewer or done after all updates

TIME & SPACE

Update Time per Query : O(1)
Reconstruction Time : O(N)
Space Complexity : O(N)

CORE IDEA

Given an array arr of size N, create a difference array diff of size N.

Definition:
diff[0] = arr[0]
diff[i] = arr[i] - arr[i - 1]

To add value x to range [L, R]:
diff[L] += x
diff[R + 1] -= x (if R + 1 < N)

Final array is obtained by prefix sum of diff.

EXAMPLE 1: Build Difference Array from Original Array

def build_difference_array(arr):
diff = [0] * len(arr)
diff[0] = arr[0]

for i in range(1, len(arr)):
    diff[i] = arr[i] - arr[i - 1]

return diff

EXAMPLE 2: Apply Range Updates Using Difference Array

Problem:
Given an array of size N, apply multiple updates of the form:
add value x to all elements from index L to R (inclusive).

def apply_range_updates(n, updates):
diff = [0] * n

for left, right, value in updates:
    diff[left] += value
    if right + 1 < n:
        diff[right + 1] -= value

return diff

EXAMPLE 3: Reconstruct Final Array from Difference Array

def reconstruct_array(diff):
arr = [0] * len(diff)
arr[0] = diff[0]

for i in range(1, len(diff)):
    arr[i] = arr[i - 1] + diff[i]

return arr

EXAMPLE 4: Full Flow Example

Problem:
Initial array of zeros, apply range updates, get final array.

def range_update_final_array(n, updates):
diff = apply_range_updates(n, updates)
return reconstruct_array(diff)

IDENTIFICATION CHECKLIST

Ask these questions:

Are there many range update operations?
Is each update additive?
Do I need the final array only after all updates?
Can prefix sums reconstruct the result?

If yes, Difference Array is the ideal technique.

COMMON PITFALLS

Forgetting to subtract at R + 1
Out-of-bounds access for R + 1
Trying to query intermediate states
Confusing difference array with prefix sum array

SUMMARY

Convert range updates into boundary updates
Apply prefix sum to reconstruct array
Massive optimization for range update problems
Foundational for advanced techniques like Imos method

Prefix Sum

Jayaprasanna Roddam — Fri, 09 Jan 2026 10:56:08 +0000

Prefix Sum

OVERVIEW

Prefix Sum is a preprocessing technique used to efficiently answer range-based
queries on arrays.

The idea is simple:

Precompute cumulative sums
Use them to answer subarray sum queries in O(1)

Instead of recomputing sums repeatedly, we reuse previously computed results.

WHEN TO USE

Use Prefix Sum when:

You are asked for sum of multiple subarrays
Queries involve ranges [L, R]
You want to reduce repeated work
The array is static (no frequent updates)

TIME & SPACE

Preprocessing Time : O(N)
Query Time : O(1)
Space Complexity : O(N)

CORE IDEA

Given an array:
arr = [a0, a1, a2, a3, ...]

Build prefix sum array:
prefix[0] = 0
prefix[i] = a0 + a1 + ... + a(i-1)

Then:
Sum of subarray [L, R] =
prefix[R + 1] - prefix[L]

EXAMPLE 1: Build Prefix Sum Array

def build_prefix_sum(arr):
prefix = [0] * (len(arr) + 1)

for i in range(len(arr)):
    prefix[i + 1] = prefix[i] + arr[i]

return prefix

EXAMPLE 2: Range Sum Query

Problem:
Find sum of elements between index L and R (inclusive).

Formula:
sum(L, R) = prefix[R + 1] - prefix[L]

def range_sum(prefix, left, right):
return prefix[right + 1] - prefix[left]

EXAMPLE 3: Subarray Sum Equals K

Problem:
Count the number of subarrays whose sum equals k.

Key Insight:
If:
prefix[j] - prefix[i] = k
Then:
prefix[i] = prefix[j] - k

Use a hashmap to track prefix sum frequencies.

def subarray_sum_equals_k(nums, k):
prefix_sum = 0
count = 0
freq = {0: 1}

for num in nums:
    prefix_sum += num

    if prefix_sum - k in freq:
        count += freq[prefix_sum - k]

    freq[prefix_sum] = freq.get(prefix_sum, 0) + 1

return count

EXAMPLE 4: Maximum Sum Subarray of Size K

Problem:
Find maximum sum of any subarray of size k.

This is a prefix-sum-based solution (sliding window optimized version exists).

def max_sum_subarray_k(arr, k):
prefix = build_prefix_sum(arr)
max_sum = float('-inf')

for i in range(len(arr) - k + 1):

    current_sum = prefix[i + k] - prefix[i]

    max_sum = max(max_sum, current_sum)

return max_sum

IDENTIFICATION CHECKLIST

Ask these questions:

Are multiple range queries involved?
Is the array static?
Do I need fast subarray sum computation?
Can subtraction of cumulative values help?

If yes, Prefix Sum is the correct approach.

COMMON PITFALLS

Off-by-one errors in indexing
Forgetting to add initial 0 in prefix array
Using prefix sum on frequently updated arrays
Assuming only positive numbers (prefix works with negatives too)

SUMMARY

Precompute once, query many times
Range sum in O(1)
Powerful when combined with hash maps
Foundational technique for many advanced problems

Fast & Slow Pointers (Cycle Detection)

Jayaprasanna Roddam — Fri, 09 Jan 2026 10:33:30 +0000

OVERVIEW

The Fast & Slow Pointers pattern uses two pointers moving through the data
structure at different speeds.

Typically:

slow moves one step at a time
fast moves two steps at a time

This pattern is most famous for detecting cycles in linked lists, but it is also
used for finding the middle of a list, cycle length, and cycle start.

WHY IT WORKS

If a cycle exists:

The fast pointer will eventually lap the slow pointer
Both pointers will meet inside the cycle

If no cycle exists:

The fast pointer will reach the end (null)

TIME & SPACE

Time Complexity : O(N)
Space Complexity : O(1)

EXAMPLE 1: Detect Cycle in a Linked List (Floyd’s Algorithm)

Problem:
Determine whether a linked list has a cycle.

Logic:

Move slow by 1 step
Move fast by 2 steps
If they ever meet, a cycle exists

class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

def has_cycle(head):
slow = head
fast = head

while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
        return True

return False

EXAMPLE 2: Find the Starting Point of the Cycle

Problem:
If a cycle exists, find the node where the cycle begins.

Key Insight:

When slow and fast meet, move one pointer to head
Move both one step at a time
The point where they meet again is the cycle start

def detect_cycle_start(head):
slow = head
fast = head

while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
        break
else:
    return None

slow = head
while slow != fast:
    slow = slow.next
    fast = fast.next

return slow

EXAMPLE 3: Find Length of the Cycle

Problem:
Given a linked list with a cycle, determine the length of the cycle.

Logic:

After slow and fast meet, keep one pointer fixed
Move the other pointer until it meets again

def cycle_length(head):
slow = head
fast = head

while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
        length = 1
        current = slow.next

        while current != slow:
            length += 1
            current = current.next

        return length

return 0

EXAMPLE 4: Find Middle of Linked List

Problem:
Return the middle node of a linked list.

Logic:

Slow moves 1 step
Fast moves 2 steps
When fast reaches end, slow is at middle

def middle_node(head):
slow = head
fast = head

while fast is not None and fast.next is not None:

    slow = slow.next

    fast = fast.next.next

return slow

IDENTIFICATION CHECKLIST

Ask these questions:

Do two pointers move at different speeds?
Is the structure sequential (linked list / array)?
Is there a cycle or repetition possibility?
Do I need middle or loop information?

If yes, Fast & Slow Pointers is the right pattern.

SUMMARY

Two pointers, different speeds
Guaranteed meeting point if cycle exists
Elegant, math-backed solution
Core interview pattern worth mastering

Two Pointers (Opposite Ends)

Jayaprasanna Roddam — Fri, 09 Jan 2026 10:24:11 +0000

"""
Two Pointers (Opposite Ends)

OVERVIEW

This pattern uses two pointers that start from opposite ends of a data structure
(array or string) and move toward each other.

It is mainly used when:

Order matters from both ends
The data is sorted or symmetric
You are checking pairs or mirrored positions
You want to reduce time complexity from O(N^2) to O(N)

POINTER SETUP

left -> starts at index 0
right -> starts at index n - 1

LOOP CONDITION

Continue while left < right

POINTER MOVEMENT LOGIC

If current condition is satisfied: update answer and move pointers
If value is too small: move left forward
If value is too large: move right backward

TIME & SPACE

Time Complexity : O(N)
Space Complexity : O(1)
"""

"""
EXAMPLE 1: Two Sum (Sorted Array)

Problem:
Given a sorted array, determine if there exists a pair whose sum equals target.

Logic:

If sum is smaller than target, increase left to get a bigger sum
If sum is larger than target, decrease right to get a smaller sum """

def two_sum_sorted(nums, target):
left = 0
right = len(nums) - 1

while left < right:
    current_sum = nums[left] + nums[right]

    if current_sum == target:
        return True
    elif current_sum < target:
        left += 1
    else:
        right -= 1

return False

"""
EXAMPLE 2: Palindrome Check

Problem:
Check whether a string is a palindrome.

Logic:

Characters at symmetric positions must match
Any mismatch immediately returns false """

def is_palindrome(s):
left = 0
right = len(s) - 1

while left < right:
    if s[left] != s[right]:
        return False

    left += 1
    right -= 1

return True

"""
EXAMPLE 3: Container With Most Water

Problem:
Find two vertical lines that together with the x-axis form a container holding
the maximum amount of water.

Logic:

Area depends on width and the smaller height
Move the pointer with the smaller height to try increasing area """

def max_area(height):
left = 0
right = len(height) - 1
max_water = 0

while left < right:
    width = right - left
    current_height = min(height[left], height[right])
    max_water = max(max_water, width * current_height)

    if height[left] < height[right]:
        left += 1
    else:
        right -= 1

return max_water

"""
EXAMPLE 4: Reverse Array In-Place

Problem:
Reverse an array without using extra space.

Logic:

Swap elements at symmetric positions
Move inward until pointers meet """

def reverse_array(arr):
left = 0
right = len(arr) - 1

while left < right:
    arr[left], arr[right] = arr[right], arr[left]
    left += 1
    right -= 1

return arr

"""

IDENTIFICATION CHECKLIST

Ask these questions:

Are two elements compared together?
Do we care about values from both ends?
Can one side be discarded every step?
Is the data sorted or symmetric?

If yes, this pattern fits.

SUMMARY

Two pointers start from opposite ends
Both move inward
Each iteration removes impossible cases
Clean, optimal, and easy to reason about """

Two Pointers (Same Direction)

Jayaprasanna Roddam — Fri, 09 Jan 2026 10:18:14 +0000

Overview

The Two Pointers (Same Direction) pattern uses two indices moving forward together through a data structure (usually an array or string).

Unlike opposite-direction pointers, both pointers only move left → right, but at different speeds or based on conditions.

This pattern is extremely common in linear-time optimizations.

When to Use Two Pointers (Same Direction)

Use this pattern when:

You process elements in order
You want to compare or relate two positions
You need to skip, filter, or track a range
You want to avoid nested loops (O(N²))

Typical Problem Statements

Remove duplicates from sorted array
Check if array is a subsequence of another
Longest substring without repeating characters
Merge two sorted arrays
Partition array based on condition
Fast & slow pointer problems (variant)

Core Intuition

Think of the pointers as:

Reader & Writer
Slow & Fast
Anchor & Explorer

One pointer represents a reference position, the other scans ahead.

General Algorithm Template

initialize slow = 0

for fast in range(0, n):
if condition satisfied:
perform operation using slow & fast
slow += 1

Both pointers move forward, but:

fast moves every iteration
slow moves only when needed

Key Properties

Time Complexity: O(N)
Space Complexity: O(1)
Works best on sorted arrays or strings
Avoids unnecessary comparisons

Example 1: Remove Duplicates from Sorted Array

Problem

Given a sorted array, remove duplicates in-place and return the new length.

Idea

fast scans elements
slow marks the position to write unique values

Code

def remove_duplicates(nums):
    if not nums:
        return 0

    slow = 0

    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1

Example 2: Check Subsequence
Problem
Check if string s is a subsequence of string t.

Idea
slow tracks position in s

fast scans t

Code

def is_subsequence(s, t):
    slow = 0

    for fast in range(len(t)):
        if slow < len(s) and s[slow] == t[fast]:
            slow += 1

    return slow == len(s)

Example 3: Longest Substring Without Repeating Characters
Problem
Find the length of the longest substring without repeating characters.

Idea
left and right both move forward

Use a set to maintain uniqueness

Code

def longest_unique_substring(s):
    seen = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1

        seen.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

Example 4: Merge Two Sorted Arrays
Problem
Merge two sorted arrays into one sorted array.

Idea
Pointer i for first array

Pointer j for second array

Both move forward

def merge_sorted(a, b):
    i = j = 0
    result = []

    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1

    result.extend(a[i:])
    result.extend(b[j:])
    return result

Difference from Sliding Window
Feature Two Pointers (Same Direction) Sliding Window
Window Concept ❌ Optional ✅ Required
Condition Simple comparison Constraint-based
Use Case Filtering / matching Optimization
Example Remove duplicates Longest subarray

Common Mistakes
Moving both pointers blindly

Forgetting pointer bounds

Using it for unsorted data when order matters

Confusing it with opposite-direction pointers

How to Identify This Pattern
Ask yourself:

Do I need to scan forward once?
Can one pointer track progress?
Is order important?
Can I replace a nested loop? If yes → Two Pointers (Same Direction)

Mental Model
Imagine:

ne pointer walks
Another pointer records
Both move forward, never backward

Summary

Aspect Two Pointers (Same Direction)
Pointers Both move left → right
Speed Different
Time O(N)
Space O(1)
Best For Filtering, matching, merging

Final Thought
This pattern is the bridge between brute force and optimal solutions.
Once mastered, you’ll instinctively replace nested loops with clean linear scans.

Sliding Window (Variable Size)

Jayaprasanna Roddam — Fri, 09 Jan 2026 08:56:55 +0000

Overview

The Variable Size Sliding Window technique is a powerful pattern used to solve problems involving subarrays or substrings where the window size is not fixed and depends on a condition.

Unlike fixed-size sliding windows, here the window expands and contracts dynamically based on constraints such as sum, frequency, distinct count, etc.

When to Use Variable Sliding Window

Use this pattern when:

You are dealing with continuous subarrays / substrings
Window size is not predefined
The problem asks for:
- Longest / Shortest subarray
- At most K / At least K / Exactly K
- A constraint that must be maintained dynamically

Typical Problem Statements

Longest subarray with sum ≤ K
Smallest subarray with sum ≥ K
Longest substring with at most K distinct characters
Minimum window substring
Longest substring without repeating characters

Core Intuition

We maintain a window [left, right] such that:

right pointer expands the window
left pointer shrinks the window when constraints are violated
The window always represents a valid candidate

General Algorithm Template

initialize left = 0
initialize required data structures (sum, hashmap, count, etc.)
initialize answer

for right in range(0, n):
include arr[right] in window

while window condition is violated:
remove arr[left] from window
left += 1

update answer using (right - left + 1)

Key Properties

Each element is visited at most twice
Time Complexity: O(N)
Space Complexity: O(1) or O(K) depending on data structures

Example 1: Longest Subarray with Sum ≤ K

Problem

Given an array of positive integers and an integer K, find the length of the longest subarray whose sum is ≤ K.

Approach

Expand right and add elements to sum
If sum > K, shrink from left
Update max length whenever window is valid

Code


python
def longest_subarray_sum_at_most_k(nums, k):
    left = 0
    window_sum = 0
    max_len = 0

    for right in range(len(nums)):
        window_sum += nums[right]

        while window_sum > k:
            window_sum -= nums[left]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len
Example 2: Smallest Subarray with Sum ≥ K
Problem
Find the length of the smallest subarray whose sum is ≥ K.

Approach
Expand window until sum ≥ K

Shrink from left to minimize window

Keep updating minimum length

Code
def smallest_subarray_sum_at_least_k(nums, k):
    left = 0
    window_sum = 0
    min_len = float('inf')

    for right in range(len(nums)):
        window_sum += nums[right]

        while window_sum >= k:
            min_len = min(min_len, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return min_len if min_len != float('inf') else 0
Example 3: Longest Substring with At Most K Distinct Characters
Problem
Given a string s, find the length of the longest substring with at most K distinct characters.

Approach
Use a frequency hashmap

Expand right, add characters

If distinct count > K, shrink from left

Code

from collections import defaultdict

def longest_substring_k_distinct(s, k):
    left = 0
    freq = defaultdict(int)
    max_len = 0

    for right in range(len(s)):
        freq[s[right]] += 1

        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len


Exactly K Pattern (Important Trick)
Problems asking for exactly K can often be solved using:

Exactly K = At Most K - At Most (K - 1)
Example
Subarrays with exactly K distinct integers

Common Mistakes
Forgetting to shrink the window

Updating answer before the window becomes valid

Using this pattern for subsequence problems (it works only for subarrays/substrings)

Applying it to arrays with negative numbers (sum-based window breaks)

Checklist to Identify Variable Sliding Window
Ask yourself:

Is the data continuous?

Is the window size dynamic?

Is there a constraint to maintain?

Can expanding and shrinking solve it in linear time?

If yes → Sliding Window (Variable)

Sliding window (Fixed length)

Jayaprasanna Roddam — Tue, 06 Jan 2026 16:36:31 +0000

Sliding Window (Fixed) — Complete Topic Explanation

The Sliding Window (Fixed) pattern is an algorithmic technique used to efficiently process all contiguous subarrays or substrings of a fixed size k.

It avoids repeated computation by reusing results from overlapping windows.

Core Idea

You are given:

A sequence (array or string)
A fixed window size k

Your task:

Perform a computation (sum, max, min, count, frequency, condition check, etc.)
For every contiguous block of size k

Instead of recomputing the result for each block independently, you:

Maintain a window of exactly k elements
Slide the window one position at a time
Update the result incrementally

Why the Naive Approach Is Inefficient

If:

Total elements = n
Window size = k

Then:

Number of windows = (n - k + 1)
Work per window = k operations

Total work:
(n - k + 1) * k

Asymptotically:
O((n - k + 1) * k) ≈ O(nk)

This becomes inefficient for large inputs.

Sliding Window Optimization Insight

When the window moves forward by one position:

One element exits the window (left side)
One element enters the window (right side)
All other elements remain unchanged

Example:
Before: [a, b, c]
After : [b, c, d]

Instead of recomputing:
b + c + d

We update:
new_value = old_value - a + d

This update takes constant time.

Algorithm Flow

Initialize variables to track the window state
Traverse the sequence from left to right
Add the current element to the window
Once the window size reaches k:
- Process or record the window result
- Remove the leftmost element
Continue until the end of the sequence

Key Characteristics

Window size is fixed
Elements are contiguous
Window slides one step at a time
Computation is incrementally updated
Eliminates nested loops

Time and Space Complexity

Metric	Complexity
Time	`O(n)`
Space	`O(1)`

When to Use Fixed Sliding Window

This pattern is applicable when:

The problem mentions subarrays or substrings
Elements must be contiguous
A fixed window size k is given
The same computation repeats over each window

Common Problem Types

Maximum / minimum sum subarray of size k
Average of all subarrays of size k
Count of vowels or characters in substrings of size k
Count of distinct elements in each window
First element satisfying a condition in every window

Mental Model

Imagine a transparent window of width k sliding across the data:

You only see k elements at a time
Each move removes one element and adds one new element
The result is updated instantly without recomputation

Summary

Fixed Sliding Window is used for contiguous, fixed-size problems
It reduces time complexity from O(nk) to O(n)
It is simple, efficient, and widely applicable
Mastering it unlocks many array and string interview problems