31 Netflix Java Developer Interview Questions & Answers

I would use two stacks: inStack for new elements and outStack for elements ready to leave the queue. enqueue pushes onto inStack. For dequeue, if outStack is empty, I move every element from inStack to outStack. This reverses the order and puts the oldest element on top. Then I pop from outStack. empty checks both stacks. enqueue is O(1), dequeue is O(1) amortized with O(n) worst case during a transfer, and auxiliary space is O(n).

The goal is to make a queue where the first value added is the first value removed. We use two stacks to do this. New values go into inStack. When we need the oldest value and outStack is empty, we move all waiting values into outStack. This reverses their order, so the oldest value becomes the next one removed. We keep using outStack until it is empty again.

1. Should dequeue throw an exception when the queue is empty?
2. Should the queue support duplicate, zero, and negative integer values?

I keep two stacks named inStack and outStack. inStack stores newly added values. outStack stores values that are ready to leave in queue order. The important invariant is that whenever outStack is not empty, its top element is the current queue front.

Both stacks start empty. Before any operation, inStack = [] and outStack = []. enqueue always pushes directly onto inStack. We do not move values during enqueue.

The operations are enqueue(10), enqueue(20), enqueue(30), dequeue(), enqueue(40), dequeue(), empty().

After enqueue(10), inStack is [10] and outStack is []. After enqueue(20), inStack is [20, 10] and outStack is []. After enqueue(30), inStack is [30, 20, 10] and outStack is [].

The first dequeue sees that outStack is empty. We transfer all values from inStack to outStack. We pop 30, then 20, then 10 from inStack and push them onto outStack. This creates outStack = [10, 20, 30], with the top shown first. Now 10 is on top, so dequeue returns 10. The state becomes inStack = [] and outStack = [20, 30].

Next, enqueue(40) pushes 40 onto inStack. The state is inStack = [40] and outStack = [20, 30].

The second dequeue does not transfer anything because outStack already contains values. It pops 20 directly. The state becomes inStack = [40] and outStack = [30]. The returned value is 20.

Finally, empty() checks both stacks. They are not both empty, so it returns false. The returned results are [10, 20, false]. The remaining logical queue order is front -> [30, 40] -> back.

Moving all values from inStack to outStack reverses their order. The oldest queued value becomes the top of outStack. As long as outStack has values, its top is the next queue front. Newer values can enter inStack, but they cannot leave before the older values already stored in outStack.

The Java code uses Deque<Integer> with ArrayDeque for both stacks. enqueue calls push on inStack. dequeue first calls moveIfNeeded(). That helper transfers values only when outStack is empty. Then dequeue checks whether the queue is empty and otherwise pops the top of outStack. empty returns true only when both stacks are empty.

enqueue is O(1). One dequeue can take O(n) when it performs a transfer, but each element moves from inStack to outStack at most once. Because of that, dequeue is O(1) amortized across many operations. empty is O(1). The two stacks together use O(n) auxiliary space. Duplicate values, negative values, and zero work normally because queue behavior depends on order, not value uniqueness. The implementation throws NoSuchElementException if dequeue is called when the queue is empty.

Use two stacks with different jobs. inStack receives every new value. outStack provides the queue front. When outStack is empty and a dequeue is requested, move every value from inStack to outStack. Moving values between stacks reverses their order, so the oldest queued element becomes the top of outStack. The central invariant is that whenever outStack is non-empty, its top is the current queue front. This avoids transferring values on every dequeue and lets each element move from inStack to outStack at most once.

enqueue takes O(1) time because it performs one push onto inStack. dequeue is O(1) amortized. One particular dequeue can take O(n) if outStack is empty and all waiting elements must move from inStack to outStack, but each element is transferred at most once before it is removed. empty takes O(1) because it only checks whether two stacks are empty. The auxiliary space is O(n) because all queue elements are stored across inStack and outStack.

A common mistake is transferring inStack into outStack on every dequeue. That does unnecessary work and loses the intended amortized performance. Another mistake is transferring new values while outStack still contains older values, which can break FIFO order. Candidates also sometimes check only one stack in empty(), even though values may exist in either stack. Another mistake is popping outStack without transferring first when it is empty. Finally, saying every dequeue is strictly O(1) is inaccurate because one dequeue can take O(n) during a transfer.

State the invariant early: whenever outStack is not empty, its top is the queue front. Then explain that you transfer from inStack only when outStack becomes empty. This makes both FIFO correctness and the O(1) amortized dequeue cost easy to explain.

I would reverse the integer one digit at a time. I repeatedly take the last digit with x % 10, remove it with x / 10, and append it to a reversed value. Before appending, I check whether multiplying by 10 and adding the digit would overflow a 32-bit signed integer. If it would, I return 0. Otherwise, I continue until x becomes 0. This takes O(d) time and O(1) auxiliary space, where d is the number of digits.

The goal is to read the digits of the number from right to left and rebuild them in that order. For example, -1203 becomes -3021. We remove one last digit at a time and add it to a new number. Before adding each digit, we check that the new number will still fit inside the allowed 32-bit signed integer range. This method fits well because it works directly with the digits and needs no extra collection. It also avoids extra storage.

1. Should I return 0 if the reversed value goes outside the 32-bit signed integer range?
2. Should negative numbers keep their negative sign in the reversed result?

The input is one 32-bit signed integer. We must return the same digits in reverse order. If the reversed number would be smaller than -2,147,483,648 or larger than 2,147,483,647, we return 0. In the diagram, the example is x = -1203, and the expected result is -3021.

We do not need an array, stack, or string. We can work directly with the integer. The expression x % 10 gives the last digit. In Java, the remainder keeps the sign of the dividend, so -1203 % 10 gives -3. Then x / 10 removes that last digit because Java integer division truncates toward zero.

The main invariant is that reversed always stores the correct reverse of the digits already removed from x.

We start with reversed = 0. The original x is -1203. We begin with the least-significant digit, which is the digit on the far right.

Before appending any new digit, we check whether reversed * 10 + digit would overflow. For the positive side, Integer.MAX_VALUE is 2,147,483,647. For the negative side, Integer.MIN_VALUE is -2,147,483,648. The important boundary value before multiplying by 10 is 214748364 or -214748364. At the positive boundary, the next digit must be at most 7. At the negative boundary, the next digit must be at least -8.

Step 1: x is -1203 and reversed is 0. We calculate digit = -1203 % 10, so digit is -3. We reduce x to -120. The overflow check is safe. We append -3, so reversed becomes -3.

Step 2: x is -120. The next digit is 0. We reduce x to -12. The check is safe. We append 0, so reversed becomes -30.

Step 3: x is -12. The next digit is -2. We reduce x to -1. The check is safe. We append -2, so reversed becomes -302.

Step 4: x is -1. The next digit is -1. We reduce x to 0. The check is safe. We append -1, so reversed becomes -3021.

Now x == 0, so the loop stops and we return -3021.

Each loop removes exactly one trailing digit from x and appends that digit to reversed. Because reversed already contains the reversed form of all previously removed digits, adding the next removed digit keeps that property true. When x becomes 0, every digit has been processed. Therefore reversed contains the complete reversed integer. The overflow checks happen before the multiplication and addition, so an invalid 32-bit result is never created.

The method keeps one integer variable called reversed. Inside the loop, it gets the last digit with %, removes that digit with /= 10, checks the positive and negative overflow boundaries, and then appends the digit. Java division truncates toward zero, and % keeps the sign of x, so the same code works for both positive and negative inputs without separate sign handling.

If the input has d digits, the loop runs at most d times, so the time complexity is O(d). The algorithm uses only a few integer variables, so the auxiliary space is O(1). Important cases are negative inputs such as -123 -> -321, trailing zeros such as 120 -> 21, zero itself, and values such as 1534236469 whose reversed form would overflow and therefore return 0.

The key idea is to build the answer from the least-significant digit to the most-significant digit. On each iteration, digit = x % 10 gives the next digit we need, and x /= 10 removes it from the remaining input. The invariant is that reversed always contains the correct reverse of the digits already removed from x. Before computing reversed * 10 + digit, we compare reversed and digit against the 32-bit boundaries. This prevents overflow instead of detecting it after it has already happened. No extra data structure is needed.

Let d be the number of digits in the integer. We process each digit at most once, so the time complexity is O(d). For a 32-bit integer, d is bounded, but O(d) clearly describes the work by number of digits. The algorithm only stores x, reversed, and the current digit. It does not create an array, string, stack, or other growing structure. Therefore the auxiliary space complexity is O(1).

A common mistake is checking for overflow only after calculating reversed * 10 + digit. At that point, the int may already have overflowed. Another mistake is using only the positive boundary and forgetting that Integer.MIN_VALUE ends in 8 while Integer.MAX_VALUE ends in 7. Candidates may also handle negative numbers separately even though Java division and remainder already make the same loop work. Another mistake is forgetting that trailing zeros disappear, so 120 becomes 21. Finally, converting to a string changes the approach and no longer matches this constant-extra-space digit algorithm.

Explain the overflow check before writing the append line. Say that you first prove reversed * 10 + digit is safe, and only then perform the multiplication and addition. This shows that you understand the main risk in the problem.

I would use vertical scanning. I take the first string as the reference and compare the same character position across every other string. If any string is too short or has a different character, I immediately return the part of the first string before that index. If every position matches, I return the whole first string. This works because all earlier positions are already confirmed. The time is O(n × m), with O(1) auxiliary space excluding the returned string.

We need to find the starting characters that every string shares. For example, with ["flower", "flow", "flight"], all three strings start with "f" and then "l". At index 2, "flower" and "flow" have "o", but "flight" has "i". So the answer is "fl". The diagram uses the first string as a reference. We compare one character position at a time across all other strings and stop as soon as a mismatch or shorter string appears.

1. Should I return an empty string when the input array is empty?
2. Is the comparison case-sensitive?
3. Can the input contain an empty string?

The input is an array of strings. We must return the longest prefix that appears at the beginning of every string. A prefix must start at index 0. We are not looking for characters that appear later in the strings.

For the example ["flower", "flow", "flight"], the required output is "fl".

I use the first string, "flower", as the reference string. I check one character position at a time. At each index i, I compare first.charAt(i) with the character at the same index in every other string.

The important invariant is simple: before processing index i, every character before i already matches in every string.

If another string ends before index i can be read, the common prefix cannot continue. If another string has a different character at index i, the common prefix also cannot continue. In either case, I return first.substring(0, i).

The reference string is first = "flower". The outer loop starts at i = 0. The other strings are "flow" and "flight".

There is no extra collection or table. The algorithm only needs the current indices, the current character, and references to the input strings.

At Step 1, i = 0. The current character is 'f'. flow[0] is 'f', and flight[0] is also 'f'. All strings match, so processing continues. The confirmed prefix is "f".

At Step 2, i = 1. The current character is 'l'. flow[1] is 'l', and flight[1] is also 'l'. All strings match again. The confirmed prefix is now "fl".

At Step 3, i = 2. The current character is 'o'. flow[2] is 'o', but flight[2] is 'i'. This is the first mismatch. The method immediately returns first.substring(0, 2), which is "fl". No later indices are processed.

Before each index i, every earlier character has already matched across every string. Therefore first.substring(0, i) is a valid common prefix.

When we find the first mismatch or the first string that is too short, no common prefix can extend beyond that position. Returning the part before that position is therefore correct. For the example, the first failure is at index 2, so "fl" is the longest common prefix.

The code first handles a null or empty array by returning "". It stores strs[0] as first. The outer loop visits each character position in first. The inner loop checks the same position in every remaining string.

The condition checks the string length before calling charAt(i). This prevents reading past the end of a shorter string. If a shorter string or mismatch is found, the code returns immediately. If every character in first matches across all strings, the method returns first.

Let n be the number of strings and m be the number of character positions examined up to the stopping point. For each position, the algorithm may compare against all n strings, so the time complexity is O(n × m). The algorithm uses O(1) auxiliary space, excluding the returned string.

Important edge cases are an empty array, one string, an empty string inside the array, a mismatch at index 0, and a shorter string that ends after some earlier characters already matched.

The key idea is vertical scanning. Use the first string as the reference and compare one character position across all strings before moving to the next position. The invariant is that before processing index i, first.substring(0, i) already matches the beginning of every string. If another string is too short or has a different character at i, no longer common prefix is possible, so returning first.substring(0, i) is correct. If every position in the first string matches, then the entire first string is the longest common prefix.

Let n be the number of strings. Let m be the number of character positions examined up to the stopping point. At each position, we may compare that character with every string. This gives O(n × m) time. The algorithm can stop early at the first mismatch or shorter string. It does not create a map, set, stack, queue, or other growing data structure, so its auxiliary space is O(1), excluding the returned string.

A common mistake is comparing whole strings instead of comparing characters at the same index. Another mistake is calling charAt(i) before checking whether a shorter string has index i, which can cause an exception. Candidates may also continue processing after the first mismatch even though the answer is already known. Another mistake is including the mismatching character in the returned substring. Finally, the complexity should match the nested comparisons: O(n × m), not O(n).

State the invariant before coding: every character before index i already matches across all strings. Then explain that the length check must happen before charAt(i), and that the algorithm returns immediately at the first mismatch because no longer common prefix can exist.

I would combine a HashMap with a doubly linked list. The map stores each key to its list node, so I can find an entry in O(1) average time. The list keeps entries from most recently used to least recently used. On every successful get or update, I move that node to the front. When capacity is exceeded, I remove the node before the tail. Each get and put takes O(1) expected time, with O(capacity) auxiliary space.

The cache can hold only a limited number of items. A get should return the stored value, or -1 when the key is missing. A put should add a new item or replace the value of an existing item. Whenever an item is used, it becomes the most recently used one. If adding a new item makes the cache too large, the least recently used item must be removed. We need one structure for quick key lookup and another structure for keeping the usage order.

1. Should get return -1 when the key is missing?
2. Should updating an existing key also make it the most recently used key?
3. Can I assume the capacity is at least 1?

I use a HashMap<Integer, Node> and a doubly linked list. The map stores key → node. This lets me find a cache entry in O(1) average time. The list stores recency order. The real node immediately after the dummy head is the most recently used entry. The real node immediately before the dummy tail is the least recently used entry.

The central invariant is that every live cache key appears exactly once in the map and exactly once in the list. The list is always ordered from most recently used to least recently used.

The map starts empty. The list contains only a dummy head and dummy tail. I connect head.next to tail and tail.prev to head. These dummy nodes avoid special cases when adding or removing nodes at either end of the list.

For get(key), I first look up the key in the map. If the key is missing, I return -1 and leave the cache unchanged. If the key exists, I remove that node from its current list position and insert it immediately after the head. This makes it the most recently used entry. Then I return its value.

For put(key, value), I first check whether the key already exists. If it does, I update the node's value and move that node to the front. If the key is new, I create a node, add it to the map, and insert it after the head. If the number of live entries is now greater than capacity, I remove tail.prev because that node is the least recently used entry. I also remove that key from the map.

The capacity is 2. The cache starts empty.

1. put(1, 10): insert key 1. State becomes [1:10]. 2. put(2, 20): insert key 2 at the front. State becomes [2:20, 1:10]. 3. get(1): key 1 is found. Move it to the front and return 10. State becomes [1:10, 2:20]. 4. put(3, 30): insert key 3. Capacity is exceeded, so evict key 2. State becomes [3:30, 1:10]. 5. get(2): key 2 is no longer in the map, so return -1. State stays [3:30, 1:10]. 6. put(4, 40): insert key 4. Capacity is exceeded, so evict key 1. State becomes [4:40, 3:30]. 7. get(1): key 1 is missing, so return -1. State stays [4:40, 3:30]. 8. get(3): key 3 is found. Move it to the front and return 30. State becomes [3:30, 4:40]. 9. get(4): key 4 is found. Move it to the front and return 40. Final state becomes [4:40, 3:30].

The complete operation-by-operation output is [null, null, 10, null, -1, null, -1, 30, 40]. The values returned by get operations are [10, -1, -1, 30, 40].

Every successful get and every put makes the affected key the most recently used entry by moving its node directly after the head. Because the list always stays in recency order, tail.prev is always the correct least recently used entry to evict. The map points directly to every live node, and an evicted key is removed from both structures.

In Java, helper methods remove a node and add a node after the head. Each helper changes only a fixed number of pointers. HashMap lookup, insertion, and removal are O(1) on average. Therefore each get and put takes O(1) expected time. The map and list hold at most the configured capacity, so auxiliary space is O(capacity).

The key insight is that the two required jobs need two cooperating data structures. A HashMap gives quick access by key, but it does not directly maintain recency order. A doubly linked list maintains recency order and lets us remove or move a known node in O(1) time. The map stores key → node. The list is ordered from MRU near the dummy head to LRU near the dummy tail. The invariant is that every live key appears exactly once in both structures, and tail.prev is always the least recently used entry. A successful get or put moves the affected node to the front. If capacity is exceeded, removing tail.prev evicts exactly the correct entry.

Each get and put takes O(1) expected time. Java HashMap lookup, insertion, and removal are O(1) on average, with normal hashing and collision caveats. Once we already have a node reference, the doubly linked list can remove that node or insert it after the head in O(1) time because only a fixed number of pointers change. The cache stores at most capacity live entries in the map and list, so auxiliary space is O(capacity).

1. Forgetting to move a node to the front after a successful get. That makes the recency order wrong.
2. Updating an existing value without refreshing its recency. A put on an existing key must also make that key most recently used.
3. Evicting tail instead of tail.prev. The tail is only a dummy node. tail.prev is the real least recently used entry.
4. Removing an evicted node from the list but forgetting to remove its key from the HashMap. The map and list would no longer represent the same live entries.
5. Updating prev and next pointers incorrectly and breaking the doubly linked list.
6. Claiming guaranteed O(1) HashMap behavior. Java HashMap operations are normally O(1) on average, so the cache operations are described as O(1) expected time.

State the invariant before writing code: the map stores key → node, the list is ordered MRU to LRU, and tail.prev is always the entry to evict. Then write remove and addAfterHead as small helpers. Once those helpers are correct, get and put become short and much easier to explain.

I would sort the meetings by start time and use a min heap to store one end time for each allocated room. The smallest value is the room that becomes available first. For each meeting, if its start time is at least that smallest end time, I reuse that room by removing the old end time. Then I add the current meeting's end time. The final heap size is the minimum rooms needed. Time is O(n log n), with O(n) auxiliary space.

We are given meeting time intervals. Each interval has a start time and an end time. We need the smallest number of rooms that can hold all meetings without putting overlapping meetings in the same room. A room can be reused when one meeting ends exactly when another starts. I sort the meetings by start time and keep one end time for each allocated room in a min heap. This makes it easy to find the room that becomes available first.

1. Can a room be reused when one meeting starts exactly when another meeting ends?
2. Can the input be empty?
3. Do you only want the minimum number of rooms, or do you also want the actual room assignments?

The input is an array of meeting intervals. Each interval is [start, end]. The output is one integer: the minimum number of rooms required. The diagram uses [[0,10],[5,15],[10,20],[20,30]]. The expected output is 2. Meetings [0,10] and [5,15] overlap, so at least two rooms are needed.

First, sort the meetings by start time. Then use a min heap. In Java, PriorityQueue is a min heap by default. Each heap value is the current end time assigned to one allocated room. The smallest heap value is the earliest end time among those rooms. If the next meeting starts at or after that value, that room can be reused. Otherwise, another room must be allocated.

After sorting, the intervals are [[0,10],[5,15],[10,20],[20,30]]. Start with an empty min heap. Put the first meeting's end time, 10, into the heap. The heap becomes [10], so one room is allocated. The invariant is that the min heap lets us find the allocated room with the earliest end time.

Step 0: Process [0,10]. Heap before: []. This is initialization, so add 10. Heap after: [10]. Rooms allocated: 1.

Step 1: Process [5,15]. Heap before: [10]. Compare start 5 with earliest end 10. Since 5 < 10, the existing room is still busy. Add 15. Heap after: [10,15]. Rooms allocated: 2.

Step 2: Process [10,20]. Heap before: [10,15]. Compare start 10 with earliest end 10. Since 10 >= 10, the room ending at 10 can be reused. Remove 10 and add 20. Heap after: [15,20]. Rooms allocated: 2.

Step 3: Process [20,30]. Heap before: [15,20]. Compare start 20 with earliest end 15. Since 20 >= 15, that room can be reused. Remove 15 and add 30. Heap after: [20,30]. Rooms allocated: 2.

All meetings are now processed. The heap size is 2, so the final answer is 2.

The heap always exposes the earliest end time among the allocated rooms. If the next meeting starts before that time, then every allocated room is still unavailable for that meeting, so another room is necessary. If the meeting starts at or after that time, the earliest finishing room can safely be reused. This keeps the number of allocated rooms as small as possible. In the example, one valid assignment is Room A: [0,10] -> [10,20] -> [20,30], and Room B: [5,15].

The code first handles null or empty input by returning 0. It sorts intervals by start time. It creates a PriorityQueue<Integer> that stores room end times. The first meeting end is inserted. For each remaining meeting, the code compares its start with minHeap.peek(). If start >= minHeap.peek(), it removes that earliest end because the room can be reused. It then inserts the current meeting's end time. After all meetings are processed, minHeap.size() is returned.

Sorting costs O(n log n). Each heap insertion or removal costs O(log n). Across all meetings, the total time is O(n log n). The heap can contain up to n end times, so auxiliary space is O(n). Important cases are empty input, touching intervals that can reuse the same room, identical overlapping intervals that may require several rooms, and one long meeting that overlaps several short meetings.

The key idea is to process meetings in start-time order while tracking the end times of allocated rooms. A min heap stores one end time for each allocated room. Its smallest value is the earliest room end time, so it tells us which room can be reused first. If the next meeting starts at or after that end time, we remove it and reuse that room. Otherwise, we allocate another room by adding the new end time without removing anything. The central invariant is that the min heap exposes the earliest end time among the allocated rooms.

Let n be the number of meetings. Sorting the intervals by start time costs O(n log n). For each remaining meeting, we insert one end time into the min heap, and we may remove one end time. Each heap insertion or removal costs O(log n). Therefore, the total time is O(n log n). The heap can grow to contain up to n end times in the worst case, so the auxiliary space is O(n).

A common mistake is treating start == earliestEnd as an overlap. The correct reuse condition is start >= earliestEnd because a room can be reused when one meeting ends exactly when another starts. Another mistake is using a max heap instead of a min heap. We need the earliest end time, so Java PriorityQueue should keep its default min-heap ordering. Candidates can also forget to sort by start time, forget to remove the earliest end before reusing its room, or claim O(n) time while ignoring the O(n log n) sorting and heap work.

State the heap invariant early: the heap stores one end time for each allocated room, and its smallest value is the earliest room end time. Then use start >= earliestEnd to explain exactly when a room can be reused.

I use two pointers, one at each end of the height array. I keep leftMax and rightMax as the tallest walls seen from each side. At every step, I process the lower side because the opposite side already gives a high enough boundary. I either update that side's maximum or add the difference as trapped water, then move that pointer inward. Each index is processed at most once. The time complexity is O(n), and the auxiliary space is O(1).

We are given a row of bars with different heights. Rain can stay above a shorter bar when taller bars form boundaries around it. We need to find the total amount of water that remains after the rain. I start from both ends and move toward the middle. I remember the tallest bar seen from each side. By always handling the lower current side, I can decide its water immediately without storing extra information for every position. This gives the required total in one pass with constant extra memory.

1. Can I assume the height values are non-negative?
2. Should I return only the total trapped water, not the amount stored at each index?
3. Is constant auxiliary space preferred if we can still keep O(n) time?

The input is an integer array called height. Each element is the height of one bar, and each bar has width 1. The output is one integer: the total number of water units trapped between the bars. For the example height = [0,1,0,2,1,0,1,3,2,1,2,1], the expected result is 6.

I keep left at the start and right at the end. I also keep leftMax and rightMax. leftMax is the tallest bar already seen from the left. rightMax is the tallest bar already seen from the right. If height[left] <= height[right], the current right bar already provides a boundary at least as high as height[left]. That means the final water at the left index depends only on leftMax. Otherwise, the same reasoning applies from the right using rightMax.

For the diagram example, left starts at index 0 with height 0. right starts at index 11 with height 1. leftMax = 0, rightMax = 0, and water = 0. The loop continues while left < right.

Step 1: left is index 0 with height 0, and right is index 11 with height 1. Since 0 <= 1, process the left side. leftMax remains 0. Move left to 1. Total water is 0.

Step 2: left is index 1 with height 1. Since 1 <= 1, process the left side. Update leftMax from 0 to 1. Move left to 2. Total water is still 0.

Step 3: left is index 2 with height

1. leftMax is 1, so this index traps 1 - 0 = 1 unit. Total becomes
2. Move left to 3.

Step 4: left is index 3 with height 2, and right is index 11 with height 1. Since the right side is lower, process it. Update rightMax from 0 to 1. Move right to 10. Total stays 1.

Step 5: left is index 3 with height 2, and right is index 10 with height 2. The code uses <=, so it processes the left side. Update leftMax from 1 to 2. Move left to 4. Total stays 1.

Step 6: left is index 4 with height

1. leftMax is 2, so add 2 - 1 = 1 unit. Total becomes
2. Move left to 5.

Step 7: left is index 5 with height 0. Add 2 - 0 = 2 units. Total becomes 4. Move left to 6.

Step 8: left is index 6 with height 1. Add 2 - 1 = 1 unit. Total becomes 5. Move left to 7.

Step 9: left is index 7 with height 3, and right is index 10 with height 2. Process the right side. Update rightMax from 1 to 2. Move right to 9. Total stays 5.

Step 10: right is index 9 with height 1. rightMax is 2, so add 2 - 1 = 1 unit. Total becomes 6. Move right to 8.

Step 11: right is index 8 with height 2. rightMax is already 2, so it remains 2. Move right to 7. Now left == right, so the loop stops. The water contributions are index 2 -> 1, index 4 -> 1, index 5 -> 2, index 6 -> 1, and index 9 -> 1. Their sum is 1 + 1 + 2 + 1 + 1 = 6.

The invariant is that leftMax is the tallest boundary seen so far from the left, and rightMax is the tallest boundary seen so far from the right. When height[left] <= height[right], the right side already guarantees a boundary at least as high as the current left bar. Therefore, the final water at left can be decided using leftMax. When the right side is lower, the same argument lets us decide the final water at right using rightMax. Once an index is processed, its trapped-water amount never needs to change.

The Java method first returns 0 for a null array or an array with fewer than three bars. It initializes left, right, leftMax, rightMax, and water. Inside the loop, it compares the two endpoint heights. It processes only the lower side, updates that side's running maximum or adds the boundary gap to water, and then moves only that pointer inward. When the two pointers meet, it returns water. The example prints 6.

Each pointer moves in only one direction, toward the middle. Therefore, each position is processed at most once, giving O(n) time. The algorithm stores only a fixed number of integer variables, so auxiliary space is O(1). Fewer than three bars trap 0 water. Strictly increasing bars, strictly decreasing bars, and equal-height bars also trap 0. Zeros and deep valleys are handled by the same boundary calculation.

The key insight is that we can decide trapped water from the lower current side without knowing every future boundary. leftMax stores the tallest bar seen so far from the left, and rightMax stores the tallest bar seen so far from the right. The invariant is that if height[left] <= height[right], the current right side already provides a boundary at least as high as height[left], so the final water at left depends only on leftMax. Otherwise, the final water at right depends only on rightMax. After processing that index, we move only its pointer inward. This gives the same boundary information using two running maxima instead of extra per-index storage.

The time complexity is O(n). The left pointer only moves to the right, and the right pointer only moves to the left. No pointer moves backward, so each position is processed at most once. The auxiliary space is O(1). Auxiliary space means extra memory used by the algorithm. We keep only left, right, leftMax, rightMax, and water, so the amount of extra memory does not grow with the input size.

One common mistake is processing the taller side instead of the lower side. That removes the reason the current water amount can be finalized safely. Another mistake is adding water before first checking whether the current bar creates a new leftMax or rightMax. Candidates may also move both pointers in one iteration instead of moving only the side that was processed. Another mistake is using extra prefix or suffix arrays but still claiming O(1) auxiliary space. Finally, this exact implementation processes the left side when height[left] <= height[right], so the walkthrough and code must use the same equality rule.

State the invariant before writing the loop: if the left bar is lower or equal, the right side already guarantees a sufficient boundary, so the left index can be finalized using leftMax. Then write the right-side branch as the mirror of that reasoning.

I would use dynamic programming. I let dp[i] store the number of valid decodings for the first i characters. I start with dp[0] = 1 and dp[1] = 1, then move left to right. At each position, I add dp[i - 1] if the last digit is 1 to 9, and dp[i - 2] if the last two digits are 10 to 26. Invalid prefixes add nothing. The time is O(n), with O(n) auxiliary space.

We are given a string that contains digits. Each number from 1 to 26 can represent one letter. We need to count how many different valid ways the whole string can be read as letters. Zero needs special care because it cannot represent a letter by itself. The main idea is to build the answer from left to right. For each position, we count ways that end with one valid digit or two valid digits. This avoids listing every possible decoding.

1. Can I assume the input contains only digit characters?
2. Should a null or empty input return 0?
3. Is returning only the number of decodings enough, without listing the decoded strings?

The input is a digit string s. The output is the number of valid ways to decode the complete string using 1 through 26 as letters A through Z. A zero cannot be decoded alone. It is valid only when it is part of 10 or 20.

For the diagram example, s = "11106". The answer is 2. The two valid decodings are 1|1|10|6, which gives AAJF, and 11|10|6, which gives KJF. The pair 06 is invalid.

I use a one-dimensional dynamic programming array named dp. Dynamic programming means I save answers for smaller prefixes and reuse them when solving a larger prefix.

The state is: dp[i] is the number of valid decodings for the first i characters, or the prefix s[0..i-1].

The central invariant is that after processing position i, dp[i] contains the correct number of valid decodings for the first i characters.

A valid decoding of a prefix can end in one of two ways. It can end with one valid digit from 1 to 9, or with one valid two-digit number from 10 to 26. These are exactly the two contributions used by the recurrence.

If s is null, empty, or starts with '0', I return 0. A string that starts with zero has no valid decoding.

For a valid non-empty string, I create dp with n + 1 entries. I set dp[0] = 1. This represents one valid way to decode an empty prefix and gives the recurrence a correct starting value. I set dp[1] = 1 because the first character is already known to be nonzero.

For s = "11106", n = 5, so the initial array is [1, 1, 0, 0, 0, 0]. Processing begins at i = 2.

At i = 2, the current character is '1'. The one-digit value 1 is valid, so I add dp[1] = 1. The two-digit value 11 is also valid, so I add dp[0] = 1. Therefore dp[2] = 2. The array becomes [1, 1, 2, 0, 0, 0].

At i = 3, the current character is '1'. The one-digit value 1 is valid, so I add dp[2] = 2. The two-digit value 11 is valid, so I add dp[1] = 1. Therefore dp[3] = 3. The array becomes [1, 1, 2, 3, 0, 0].

At i = 4, the current character is '0'. Zero cannot stand alone, so the one-digit path contributes nothing. The two-digit value is 10, which is valid, so I add dp[2] = 2. Therefore dp[4] = 2. The array becomes [1, 1, 2, 3, 2, 0].

At i = 5, the current character is '6'. The one-digit value 6 is valid, so I add dp[4] = 2. The final two characters are "06". The code computes their numeric value as 6, which is outside the valid two-digit range 10 through 26, so that path contributes nothing. Therefore dp[5] = 2. The final array is [1, 1, 2, 3, 2, 2].

The result is read from dp[5], so the method returns 2.

Every valid decoding of the first i characters must end with either one valid digit or one valid two-digit code. If the last digit is from 1 to 9, every valid decoding counted by dp[i - 1] can be extended with that digit. If the last two digits form a value from 10 to 26, every decoding counted by dp[i - 2] can be extended with that pair. Invalid endings add zero. These cases cover all valid endings without counting an invalid one.

The Java code first rejects null, empty, and leading-zero inputs. It creates an int array of size n + 1 and sets the two base cases. It then processes i from 2 through n. Character arithmetic converts the current character to oneDigit and combines the previous and current characters into twoDigit without creating substring objects. The code adds the correct previous dp value only when that ending is valid. Finally, it returns dp[n].

The loop processes each position once, so the time complexity is O(n). The dp array has n + 1 entries, so the auxiliary space is O(n).

Important cases are a string starting with '0', which returns 0, valid zero pairs such as 10 and 20, invalid pairs such as 06, and prefixes such as 30 where zero cannot be used alone. A null or empty string also returns 0 defensively.

The key insight is that a valid decoding of a prefix can end in only two possible ways: one valid digit from 1 to 9, or one valid two-digit value from 10 to 26. I define dp[i] as the number of valid decodings for the first i characters. If the one-digit ending is valid, dp[i - 1] contributes to dp[i]. If the two-digit ending is valid, dp[i - 2] contributes. Invalid endings contribute nothing. The invariant is that each computed dp[i] is the correct count for that prefix. Reusing these prefix counts avoids enumerating every complete decoding.

Let n be the number of characters in the string. We move from left to right and process each position once, so the time complexity is O(n). We create a dynamic programming array with n + 1 integer entries, so the auxiliary space is O(n). Auxiliary space means extra memory used by the algorithm. The code does not create substrings for each check. It uses character arithmetic to calculate the one-digit and two-digit values.

A common mistake is treating '0' as a valid letter by itself. Another is accepting a two-digit value outside 10 through 26. Candidates also sometimes forget that 10 and 20 are valid even though their final digit is zero. Another mistake is adding dp[i - 1] when the current digit is zero. It is also easy to initialize dp[0] incorrectly. dp[0] must be 1 so a valid two-digit code at the beginning can contribute correctly.

State the dp meaning before writing the recurrence: "dp[i] is the number of ways to decode the first i characters." Then check the one-digit ending and two-digit ending separately. This makes the handling of zero much easier to explain and code correctly.