Skip to main content

One Pass

Looking for Missing Number (268)? Its one-pass solution is an XOR fold, so it lives with the rest of the XOR technique in Bit Manipulation / XOR.

Running Extremes​

Second Largest​

Easy·
Explanation

Find the second largest element in a single scan, without sorting and without a second pass. We carry two running maxima and update them in a cascade as larger values appear.

Scan:

  • For each value, if it beats the current first_max, the old first_max cascades down into second_max and the new value becomes first_max.
  • Otherwise, if it sits strictly between second_max and first_max, it becomes the new second_max. The strict checks (first_max > i and second_max < i) skip duplicates of the maximum so they never pollute the runner-up.

Result:

  • second_max stays -1 when there is no valid runner-up (for example, when every element is identical).
Analysis
Time
O(N)
  • N is the number of elements in the array. Each element is compared a constant number of times.
Space
O(1)
  • Only the two running maxima are stored.
FIG. SECOND LARGEST● INTERACTIVE
visualization loads as you reach it
class Solution:
def getSecondLargest(self, arr):
first_max, second_max = -1, -1
for i in arr:
if first_max < i:
second_max = first_max
first_max = i
elif first_max > i and second_max < i:
second_max = i
return second_max

1796. Second Largest Digit in a String​

Easy·
Explanation

The same two-running-maxima idea as Second Largest, specialised to the digit characters embedded in a string. Non-digit characters are simply skipped, and the comparison happens directly on the character codes (which order correctly for the digits '0'-'9').

Scan:

  • Skip any character that is not a digit with continue.
  • On a larger digit, cascade the old first_max down into second_max and store the new one.
  • Otherwise, if the digit lands strictly between the two maxima, it becomes the new second_max.

Result:

  • The sentinel "-" marks "no digit yet". If second_max never advances past it, the answer is -1; otherwise the surviving digit character is converted back to an int.
Analysis
Time
O(n)
  • n = len(s). The for i in s loop inspects each character once.
Space
O(1)
  • Only the two running maxima, first_max and second_max, are stored.
FIG. 1796 SECOND LARGEST DIGIT IN A STRING● INTERACTIVE
visualization loads as you reach it
class Solution:
def secondHighest(self, s: str) -> int:
first_max = second_max = "-"
for i in s:
if not i.isdigit():
continue
if first_max < i:
second_max = first_max
first_max = i
elif first_max > i and second_max < i:
second_max = i
 
# print(first_max, second_max)
return int(second_max) if second_max != "-" else -1

Greedy Scan​

2259. Remove Digit From Number to Maximize Result​

Easy·
Explanation

We must delete exactly one occurrence of digit to leave the largest possible number. Removing a digit shifts everything after it one place left, so the result grows most when the digit we drop is immediately followed by a larger digit.

Greedy scan:

  • Walk left to right. At each occurrence of digit, peek at the next character number[i + 1].
  • If that next character is larger, deleting here promotes a bigger digit into this position - that is provably optimal, so return immediately.
  • Otherwise remember this index in last_occ; a later occurrence might still pay off.

Fallback:

  • If no occurrence had a larger successor, the best move is to delete the last occurrence (including the final character, handled after the loop), since that disturbs the highest-value prefix the least.
Analysis
Time
O(N)
  • N is the number of digits. A single left-to-right scan finds the deletion point.
Space
O(N)
  • The returned string slices allocate a new string of length N - 1.
FIG. 2259 REMOVE DIGIT FROM NUMBER TO MAXIMIZE RESULT● INTERACTIVE
visualization loads as you reach it
class Solution:
def removeDigit(self, number: str, digit: str) -> str:
n = len(number)
last_occ = 0
for i in range(n - 1):
if number[i] == digit:
if number[i + 1] > digit:
return number[:i] + number[i + 1 :]
last_occ = i
if number[-1] == digit:
last_occ = n - 1
return number[:last_occ] + number[last_occ + 1 :]

605. Can Place Flowers​

Easy·
Explanation

Flowers can't be adjacent, so a 0 is plantable only when both neighbors are also empty (or off the edge). Planting there the moment we see it is always safe: it never blocks a future placement, since the next possible slot is at least two cells away either way.

Greedy scan:

  • Walk left to right. At each 0, check flowerbed[i - 1] and flowerbed[i + 1] (treating out-of-bounds as empty).
  • If both sides are empty, plant here (flowerbed[i] = 1) and decrement n.
  • Stop early once n <= 0.
Analysis
Time
O(size)
  • The for i in range(size) loop runs unconditionally to the end (it never breaks early even after n <= 0), doing O(1) work per cell, so total is O(size), where size = len(flowerbed).
Space
O(1)
  • Planting happens in place on the input array; no extra structures are allocated.
FIG. 605 CAN PLACE FLOWERS● INTERACTIVE
visualization loads as you reach it
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
size = len(flowerbed)
for i in range(size):
if flowerbed[i] == 0:
empty_left = (i == 0) or (flowerbed[i - 1] == 0)
empty_right = (i == size - 1) or (flowerbed[i + 1] == 0)
if empty_right and empty_left:
flowerbed[i] = 1
n -= 1
return n <= 0

Neighbor Lookup​

Neither a window nor a running extreme - each position's answer depends only on the value sitting right next to it, so a single pass that reads one neighbor per index is enough, whichever direction it walks.

1844. Replace All Digits with Characters​

Easy·
2 Approachesclick to switch
Explanation

s always has odd length with a letter at every even index and a digit at every odd index, so the last character is always a letter with nothing after it - ans.append(s[-1]) handles it up front, and n is dropped by one to exclude it from the loop. Walking i backward two at a time then lands on exactly the digit positions: s[i] is the shift amount, s[i-1] is the letter it applies to, and shifted_char is that letter advanced shift places with %26 wraparound. Both the untouched letter and its shifted neighbor are pushed onto the front of ans together, in that order, so each pair lands in the deque exactly where it sat in s.

Analysis
Time
O(2n + 26)
  • The backward pairwise scan and the final "".join(ans) are each a separate O(n) pass - 2n combined, where n = len(s).
  • alphabet_map is built once from the 26-character alphabet, O(26), independent of n.
Space
O(n + 26)
  • ans holds all n characters before the join.
  • alphabet_map holds exactly the 26 letters of the alphabet, O(26), independent of n.
FIG. 1844 REPLACE ALL DIGITS WITH CHARACTERS BACKWARD● INTERACTIVE
visualization loads as you reach it
class Solution:
def replaceDigits(self, s: str) -> str:
n = len(s)
ans = collections.deque()
alphabets = "abcdefghijklmnopqrstuvwxyz"
alphabet_map = {j: i for i, j in enumerate(alphabets)}
if n % 2:
ans.append(s[-1])
n -= 1
for i in range(n - 1, -1, -2):
# print(i)
shift = int(s[i])
char = s[i - 1]
shifted_char = alphabets[(alphabet_map[char] + shift) % 26]
ans.appendleft(shifted_char)
ans.appendleft(char)
return "".join(ans)