Excel Sheet Column Number

▶

Steps

setup

Initialize variables

We determine the length of the input string 'A' and initialize the powers array with 1s for each character position.

💡 Initializing the powers array is essential because it will hold the powers of 26 needed to convert each character to its numeric value.

Line:

n = len(columnTitle)
powers = [1] * n

💡 The length of the input determines how many powers of 26 we need to compute.

expand

Compute powers of 26 (start from right)

Since the input length is 1, no iteration is needed to compute powers beyond the initialized 1 at the last position.

💡 For longer inputs, this step computes powers of 26 from right to left, but here it confirms the base case.

Line:

for i in range(n - 2, -1, -1):
    powers[i] = powers[i + 1] * 26

💡 The powers array remains [1], representing 26^0 for the single character.

setup

Initialize result accumulator

We initialize the result variable to zero before starting to process each character.

💡 The result variable will accumulate the total column number as we process each character.

Line:

result = 0

💡 Starting with zero ensures the sum of contributions from each character is accurate.

traverse

Start iterating over characters

We begin iterating over the input string 'A' from left to right, starting at index 0.

💡 Processing characters left to right aligns with the positional powers computed earlier.

Line:

for i, ch in enumerate(columnTitle):

💡 The pointer 'i' indicates which character is currently being processed.

compare

Convert character to numeric value

We convert the character 'A' to its numeric value by subtracting 'A' and adding 1, resulting in 1.

💡 This conversion maps 'A' to 1, 'B' to 2, ..., 'Z' to 26, matching Excel column numbering.

Line:

value = ord(ch) - ord('A') + 1

💡 Each character's numeric value represents its contribution in base-26.

expand

Multiply numeric value by power of 26

We multiply the numeric value 1 by the power of 26 at index 0, which is 1, resulting in 1.

💡 Multiplying by the power of 26 scales the character's value according to its position.

Line:

result += value * powers[i]

💡 This step shows how positional value affects the total column number.

insert

Update running result

We add the product 1 to the running result, updating it from 0 to 1.

💡 Accumulating the sum builds the final column number step by step.

Line:

result += value * powers[i]

💡 The running total now reflects the contribution of all processed characters.

traverse

End of iteration

We have processed all characters in the input string, so the iteration ends.

💡 Completing the iteration means the final result is ready to be returned.

Line:

for i, ch in enumerate(columnTitle):
    ...
return result

💡 The accumulated result now represents the full column number.

reconstruct

Return final result

The function returns the accumulated result, which is 1 for input 'A'.

💡 Returning the result completes the algorithm and provides the final answer.

Line:

return result

💡 The final output matches the expected Excel column number for 'A'.

reconstruct

Final state summary

The algorithm has completed, and the final answer is 1, corresponding to the input 'A'.

💡 This final state confirms the correctness of the algorithm for the simplest case.

💡 The visualization ends with the final answer clearly shown.

def titleToNumber(columnTitle: str) -> int:
    n = len(columnTitle)  # STEP 1
    powers = [1] * n      # STEP 1
    for i in range(n - 2, -1, -1):  # STEP 2
        powers[i] = powers[i + 1] * 26
    result = 0            # STEP 3
    for i, ch in enumerate(columnTitle):  # STEP 4
        value = ord(ch) - ord('A') + 1    # STEP 5
        result += value * powers[i]       # STEP 6 & 7
    return result          # STEP 9

if __name__ == '__main__':
    test_cases = ['A', 'AB', 'ZY']
    for case in test_cases:
        print(f"{case} -> {titleToNumber(case)}")

📊

Excel Sheet Column Number - Watch the Algorithm Execute, Step by Step

Watching each step reveals how base-26 encoding works and how each character contributes to the final number, making the process intuitive without needing to parse code.

setup

n

1

0

Result: 0

expand

1

0

Result: 0

setup

1

0

Result: 0

traverse

i

1

0

Result: 0

compare

i

1

0

Result: 0

expand

i

1

0

Result: 0

insert

i

1

0

Result: 1

traverse

1

0

Result: 1

reconstruct

1

0

Result: 1

reconstruct

1

0

Result: 1

Key Takeaways

✓ Each character in the Excel column title corresponds to a digit in a base-26 number system.

This insight is hard to see from code alone because the base-26 encoding is implicit in the arithmetic, but the visualization makes it explicit.

✓ Computing powers of 26 from right to left prepares the correct multiplier for each character's position.

Seeing the powers array visually clarifies why each character is multiplied by a different power depending on its position.

✓ Accumulating the sum of each character's value times its power yields the final column number.

The step-by-step addition shows how partial sums build up to the final answer, which is less obvious when reading code.

Practice

1. Consider the following code snippet that checks if a number is a palindrome by reversing half of its digits. What is the value of reversed_half after the second iteration of the while loop when input is 12321?

easy

A. 12

B. 1

C. 21

D. 123

Solution

1. Step 1: Trace first iteration

   Initial x=12321, reversed_half=0 reversed_half = 0*10 + 12321%10 = 1 x = 12321 // 10 = 1232

2. Step 2: Trace second iteration

   reversed_half = 1*10 + 1232%10 = 10 + 2 = 12 x = 1232 // 10 = 123

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After two iterations reversed_half is 12 [OK]

Hint: Track variable updates carefully each loop iteration [OK]

Common Mistakes:

• Off-by-one iteration count
• Mixing x and reversed_half values
• Incorrect modulo or division

2. You need to find the nth number whose prime factors only include 2, 3, and 5. Which approach guarantees an optimal solution that efficiently generates these numbers without checking every integer sequentially?

easy

A. Use a min-heap (priority queue) to always extract the smallest candidate and generate new multiples, avoiding duplicates.

B. Use a greedy algorithm that picks the smallest next multiple of 2, 3, or 5 from previously found numbers.

C. Use dynamic programming with a 2D table to store all factors and their counts for each number up to n.

D. Use brute force by checking each integer sequentially and verifying if its prime factors are only 2, 3, and 5.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating numbers whose prime factors are only 2, 3, and 5, known as ugly numbers.

2. Step 2: Evaluate approaches for efficiency and correctness

   Brute force is too slow; min-heap approach is efficient but can be optimized further; dynamic programming with a 2D table is overcomplicated. The greedy approach with three pointers picks the smallest next multiple of 2, 3, or 5 from previously found numbers, efficiently generating the sequence without duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three-pointer greedy approach efficiently generates ugly numbers in ascending order without duplicates [OK]

Hint: Three-pointer greedy approach avoids duplicates and generates numbers in order [OK]

Common Mistakes:

• Assuming min-heap is the only efficient approach
• Thinking DP with 2D table is needed for prime factorization
• Believing brute force is efficient enough for large n

3. What is the time complexity of the optimal rectangle overlap check algorithm that uses min and max coordinate comparisons?

medium

A. O(1), constant time since only coordinate comparisons are done

B. O(n^2), checking all pairs of points between rectangles

C. O(log n), due to sorting of coordinates

D. O(n), where n is the number of points inside the rectangles

Solution

1. Step 1: Identify operations performed

   The algorithm only performs a fixed number of min and max operations on rectangle coordinates.

2. Step 2: Recognize no loops or recursion involved

   Since no iteration over points or sorting is done, the time complexity is constant.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only a few arithmetic and comparison operations -> O(1) [OK]

Hint: No loops or recursion means O(1) time [OK]

Common Mistakes:

• Assuming complexity depends on rectangle size or points inside
• Confusing coordinate comparisons with sorting
• Thinking overlap check requires scanning all points

4. The following code attempts to check if two rectangles overlap. Which line contains a subtle bug that causes incorrect results when rectangles only touch at edges or corners?

medium

A. Line 4: Return condition using '>=' instead of '>'

B. Line 2: Calculation of x_overlap

C. Line 1: Function definition

D. Line 3: Calculation of y_overlap

Solution

1. Step 1: Understand overlap condition

   Rectangles overlap only if overlap length on both axes is strictly greater than zero.

2. Step 2: Identify the bug in return condition

   Using '>=' returns true even when rectangles just touch edges (overlap = 0), which is incorrect.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Change '>=' to '>' fixes false positives on touching edges [OK]

Hint: Overlap must be strictly positive, not zero [OK]

Common Mistakes:

• Using '>=' instead of '>' in overlap check
• Mixing up min and max in coordinate calculations
• Ignoring one axis overlap

5. What is the time complexity of the min-heap based algorithm to find the nth ugly number, and why might a common misconception about it be incorrect?

medium

A. O(n^2) because each number can generate up to 3 new numbers leading to quadratic growth.

B. O(n) because each number is processed exactly once without duplicates.

C. O(n log n) because each of the n iterations involves popping and pushing in a heap of size up to n.

D. O(n log k) where k is the number of unique ugly numbers generated, which is less than n.

Solution

1. Step 1: Identify operations per iteration

   Each iteration pops one element from the heap and pushes up to 3 new elements if unseen.

2. Step 2: Analyze heap size and operations

   The heap size can grow up to O(n) because duplicates are avoided. Each push/pop operation costs O(log n), so total time is O(n log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Heap operations dominate complexity, confirming O(n log n) [OK]

Hint: Heap push/pop cost dominates, not just number of elements [OK]

Common Mistakes:

• Assuming linear time because each number is processed once
• Thinking complexity is quadratic due to multiple pushes per iteration
• Confusing k (unique numbers) with n (iterations)