36 Apple Java Developer Interview Questions & Answers

I would use Kadane’s algorithm. I keep currentSum as the best contiguous subarray sum ending at the current position, and maxSum as the best sum seen anywhere so far. I start both with nums[0], then move from index 1 to the end. At each value, I either start a new subarray or extend the previous one, whichever gives the larger sum. This works in O(n) time and uses O(1) auxiliary space.

The problem gives an integer array and asks for the largest sum we can get from one continuous part of that array. The numbers must stay next to each other, so we cannot skip elements. The main idea is to move from left to right and remember the best sum that can end at the current position. We also remember the best sum found anywhere so far. This avoids checking every possible continuous part of the array and gives a simple linear-time solution.

1. Can I assume the input array has at least one element?
2. Do you only need the maximum sum, or should I also return the subarray itself?

The input is an integer array called nums. The output is one integer: the maximum possible sum of a contiguous subarray. Contiguous means the chosen elements must be next to each other in the original array. For the example nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], the answer is 6 because the contiguous subarray [4, -1, 2, 1] has sum 6.

I use Kadane’s algorithm because I do not need to keep every possible subarray. At each index, I only need two values. currentSum is the best sum of a contiguous subarray that ends at the current index. maxSum is the best subarray sum seen anywhere so far. The key decision is simple: either start a new subarray at nums[i], or extend the previous subarray by adding nums[i].

At index 0, nums[0] is -2. I set currentSum = -2 and maxSum = -2. Initializing with the first array value is important. If I started both values at 0, an all-negative array could incorrectly return 0 even though 0 is not the maximum sum of any non-empty contiguous subarray.

At i = 1, nums[i] = 1. Starting new gives 1. Extending gives -2 + 1 = -1. I choose 1, so currentSum becomes 1 and maxSum becomes 1.

At i = 2, nums[i] = -3. Starting new gives -3. Extending gives 1 + -3 = -2. I choose -2, so currentSum becomes -2 and maxSum stays 1.

At i = 3, nums[i] = 4. Starting new gives 4. Extending gives -2 + 4 = 2. Starting again is better, so currentSum becomes 4 and maxSum becomes 4.

At i = 4, nums[i] = -1. Starting new gives -1. Extending gives 4 + -1 = 3. I extend, so currentSum becomes 3 and maxSum stays 4.

At i = 5, nums[i] = 2. Starting new gives 2. Extending gives 3 + 2 = 5. I extend, so currentSum becomes 5 and maxSum becomes 5.

At i = 6, nums[i] = 1. Starting new gives 1. Extending gives 5 + 1 = 6. I extend, so currentSum becomes 6 and maxSum becomes 6. This builds the best subarray [4, -1, 2, 1].

At i = 7, nums[i] = -5. Starting new gives -5. Extending gives 6 + -5 = 1. I extend, so currentSum becomes 1 and maxSum stays 6.

At i = 8, nums[i] = 4. Starting new gives 4. Extending gives 1 + 4 = 5. I extend, so currentSum becomes 5 and maxSum stays 6. After all elements are processed, I return 6.

The important invariant is that currentSum always stores the maximum sum of any contiguous subarray ending at the current index. A best subarray ending at i has only two possibilities: it starts at i, or it extends the best subarray ending at i - 1. Taking the larger of nums[i] and currentSum + nums[i] therefore keeps currentSum correct. maxSum records the largest currentSum seen during the traversal, so after the final element it is the maximum subarray sum over the whole array.

The Java solution keeps the same class and maxSubArray method shown in the diagram. It initializes currentSum and maxSum with nums[0]. The loop starts at index 1. For each element, Math.max(nums[i], currentSum + nums[i]) decides whether to start fresh or extend the previous subarray. Then Math.max(maxSum, currentSum) updates the best overall result. A small main method runs the exact diagram example and prints 6.

The loop processes each array position once, so the time complexity is O(n). The algorithm only keeps a few integer variables, so the auxiliary space complexity is O(1). Important edge cases are an array with one element, an array containing only negative values, zeros mixed with negative values, and an array containing only positive values. For an all-positive array, the whole array is optimal. For an all-negative array, the largest single value is returned.

The key insight is that when I reach index i, I do not need to remember every earlier subarray. I only need the best contiguous sum that ended at i - 1. For nums[i], there are exactly two useful choices: start a new subarray with nums[i], or extend the previous best ending sum with currentSum + nums[i]. I keep the larger result as the new currentSum. The central invariant is that currentSum is always the best contiguous subarray sum ending at the current index. maxSum keeps the largest currentSum seen so far. This avoids checking many different subarrays separately.

The time complexity is O(n), where n is the number of elements in nums. We move through the array once from left to right and do constant work at each position. The auxiliary space complexity is O(1). Auxiliary space means extra memory used by the algorithm. We only keep currentSum, maxSum, and the loop index, so the extra memory does not grow as the input becomes larger.

A common mistake is initializing currentSum and maxSum to 0. That fails for an all-negative input such as [-5, -1, -8], where the correct result is -1. Another mistake is updating the running sum but forgetting to keep maxSum for the best result seen earlier. Some candidates incorrectly choose non-contiguous elements, which solves a different problem. Another mistake is always extending the previous sum instead of comparing it with nums[i], so a harmful negative prefix is never discarded. Candidates may also claim O(n) extra space even though this implementation uses only O(1) auxiliary space.

State the invariant before writing the loop: currentSum is the best contiguous sum ending at the current index, and maxSum is the best sum seen anywhere. Then explain each Math.max line using that invariant.

I would binary-search the shorter array and choose a partition in it. That partition determines the matching partition in the other array, so the left side contains exactly (m + n + 1) / 2 elements. I check the two cross-boundary conditions. If one fails, I move the binary-search range left or right. When both hold, the boundary values give the median. This takes O(log(min(m, n))) time and O(1) auxiliary space.

We have two arrays that are already sorted. We need the middle value if we imagine both arrays as one sorted list, but we do not want to build that full list. The key idea is to split both arrays so the left side contains the required number of values. We binary-search the shorter array to find the correct split. Once every value on the left is less than or equal to every value on the right, the middle boundary values give the answer.

1. Can one of the two sorted arrays be empty?
2. Can I assume the combined input contains at least one value?

Let A be the shorter array and B be the longer array. Let m and n be their lengths. We search only partition positions in A. This keeps the search range as small as possible.

For the diagram example, A = [1, 2] and B = [3, 4]. We have m = 2 and n = 2. The required left-side size is half = (m + n + 1) / 2 = 2.

Set low = 0 and high = m. These bounds are inclusive because a valid partition can be before the first element or after the last element of A.

A partition position i in A determines the partition j in B with j = half - i. This keeps the total number of values on the left side fixed at half.

Initially, low = 0 and high = 2. The midpoint is i = 1, so j = 1.

The boundary values are Aleft = 1, Aright = 2, Bleft = 3, and Bright = 4. A valid partition needs Aleft <= Bright and Bleft <= Aright.

The first condition is true, but Bleft <= Aright is false because 3 > 2. This means A's partition is too far left. We move right by setting low = i + 1 = 2.

Now low = 2 and high = 2. The midpoint is i = 2, so j = 0.

The boundaries are Aleft = 2, Aright = +infinity, Bleft = -infinity, and Bright = 3. Both cross-boundary checks are now true. The partition is valid, so the search stops.

The combined length is even. The two middle values are max(Aleft, Bleft) = 2 and min(Aright, Bright) = 3. The median is (2 + 3) / 2 = 2.5.

The two left partitions always contain exactly half = (m + n + 1) / 2 elements. Because each input array is sorted, the only possible ordering violations are across the two partition boundaries. When Aleft <= Bright and Bleft <= Aright, every value on the left belongs before every value on the right. Therefore, the median is determined by the partition boundary values.

The Java code first swaps the array references when needed so A is always the shorter array. It uses Integer.MIN_VALUE and Integer.MAX_VALUE as sentinels when a partition touches an array boundary. Each failed partition removes part of the remaining binary-search interval. When a valid partition is found, the code returns either the largest left boundary for an odd total length or the average of the two middle boundaries for an even total length.

The binary search is performed only on the shorter array, so the time complexity is O(log(min(m, n))). The algorithm uses only a fixed number of variables, so auxiliary space is O(1). Important cases shown by the diagram include one array being empty, duplicate values, an odd combined length, and a partition at the beginning or end of an array.

The key insight is that we do not need to merge the arrays. We only need the point where the combined sorted order is divided into a left part and a right part. Binary-search a partition i in the shorter array. Compute the matching partition j = half - i in the other array, where half = (m + n + 1) / 2. The invariant is that the two left partitions always contain exactly half elements. If Aleft > Bright, move the partition in A left. If Bleft > Aright, move it right. When both cross-boundary comparisons hold, the partition is correct and the median comes directly from the boundary values.

Let m and n be the two array lengths. We binary-search only the shorter array, so the time complexity is O(log(min(m, n))). Each iteration reads a constant number of array values and performs a constant number of comparisons. The algorithm does not create a merged array or another growing data structure. It uses only variables for the search bounds, partition indices, and boundary values. Therefore, the auxiliary space complexity is O(1).

A common mistake is binary-searching the longer array, which loses the intended O(log(min(m, n))) bound. Another is computing j independently instead of using j = half - i, which breaks the fixed left-side size. Candidates also move the search range in the wrong direction when a cross-boundary check fails. Boundary partitions must use safe sentinel values or equivalent checks. For an even combined length, the median must use max(Aleft, Bleft) and min(Aright, Bright), not values from only one array. The average should be evaluated as a floating-point calculation rather than integer division.

State the partition invariant before coding: the two left partitions together always contain half = (m + n + 1) / 2 elements. Then explain that the two cross-boundary comparisons tell you whether to move left, move right, or return the median.

I would scan the grid from top-left to bottom-right. When I find a land cell, '1', I count a new island and start DFS from that cell. DFS marks every horizontally or vertically connected land cell as '0', so the same island cannot be counted again. I continue until the full grid is scanned. The total time is O(m × n), and the recursive DFS can use O(m × n) auxiliary space in the worst case.

We have a grid containing land marked '1' and water marked '0'. We need to count how many separate groups of land exist. Land belongs to the same group only when cells touch up, down, left, or right. Diagonal touching does not join groups. I scan the grid in order. When I find land that has not already been handled, I count one new group and visit all connected land from that cell. I mark those cells so they cannot be counted again.

1. Can I modify the input grid while processing it?
2. Should diagonal land cells be treated as disconnected? In this problem, only up, down, left, and right connections count.

The input is an m × n grid of characters. A '1' means land and a '0' means water. The output is one integer: the number of separate islands. Two land cells are connected only through up, down, left, or right moves. Diagonal contact does not connect them.

The diagram uses this exact 4 × 5 example: 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1

The expected result is 3.

I use depth-first search, or DFS. DFS starts from one land cell and visits its whole connected component. A connected component means all land cells reachable from each other using the four allowed directions.

Instead of keeping a separate visited array, the solution changes each visited '1' to '0'. The central invariant is simple: once a land cell has been visited and changed to '0', it cannot cause the same island to be counted again.

If the grid is null or empty, the method returns 0. Otherwise, it stores the row count and column count and sets islands to 0.

The two loops scan cells row by row from top-left to bottom-right. Whenever grid[r][c] is '1', that cell is the first unvisited cell of a new island. The algorithm increments islands and starts DFS from that position.

The scan first reaches (0,0), which contains '1'. islands changes from 0 to 1. DFS marks (0,0), (0,1), (1,0), and (1,1) as '0'. This removes the complete 2 × 2 island from future counting.

The scan continues until (2,2), which still contains '1'. islands changes from 1 to 2. DFS marks (2,2). Its four neighbors do not contain connected land, so this island contains one cell.

The scan later reaches (3,3), which contains '1'. islands changes from 2 to 3. DFS marks (3,3) and (3,4). This removes the final two-cell island.

The scan then completes. The method returns 3. The three components are {(0,0),(0,1),(1,0),(1,1)}, {(2,2)}, and {(3,3),(3,4)}.

Every island has a first land cell reached by the row-by-row scan. When that first unvisited '1' is found, the count increases exactly once. DFS then changes every four-directionally connected land cell in that island to '0'. Because those cells are no longer '1', no later scan position can count the same island again. Therefore, every island is counted exactly once.

numIslands handles the empty-input case first. It then scans every grid position. When the current cell is '1', it increments islands and calls dfs.

The DFS base case returns when the coordinates are outside the grid or the current cell is already '0'. For valid land, DFS immediately changes the cell to '0'. It then recursively explores down, up, right, and left. Marking the cell before recursion prevents repeated visits. After the outer scan finishes, numIslands returns islands.

The time complexity is O(m × n), where m is the number of rows and n is the number of columns. The outer scan examines the grid, and each land cell is marked visited once. The DFS work across the whole grid remains O(m × n).

The worst-case recursion stack is O(m × n), such as when one large island contains most or all cells. Relevant edge cases are an empty grid, an all-water grid, one large island, diagonal land that must stay disconnected, and scattered single-cell islands. If the input grid cannot be modified, a boolean[][] visited array can be used instead.

The key idea is to count connected components. Scan the grid from top-left to bottom-right. Each time a remaining '1' is found, it must belong to an island that has not been counted yet. Increment the island count and run DFS from that cell. DFS visits the entire four-directionally connected component and changes every visited land cell to '0'. The central invariant is that once a land cell is marked '0', that cell cannot start another island later. This makes each connected component contribute exactly one to the final count.

Let m be the number of rows and n be the number of columns. The time complexity is O(m × n). The grid is scanned once, and DFS marks each land cell as visited so it does not need to be explored again as land. The worst-case auxiliary space is O(m × n) because recursive DFS calls can become that deep when one very large island fills the grid. The solution does not need a separate visited matrix because it stores the visited state directly in the input grid by changing '1' to '0'.

A common mistake is treating diagonal land cells as connected even though only up, down, left, and right connections count. Another mistake is marking a land cell after recursive calls instead of before them, which can cause repeated visits. Candidates may also forget the out-of-bounds DFS base case. Another error is saying the solution uses O(1) auxiliary space even though recursive DFS can use O(m × n) stack space. Finally, if the interviewer does not allow input mutation, changing '1' to '0' is not acceptable and a separate visited structure is needed.

Explain the invariant before writing the DFS: every remaining '1' found by the scan starts exactly one new island, and DFS immediately changes that whole four-directionally connected component to '0'. That makes the counting logic and correctness easy to justify.

I would keep the lowest stock price seen so far and the best profit found so far. I start with the first price as minPrice, then move from left to right. For each later price, I calculate the profit if I sell today. I update maxProfit when that profit is better, and I update minPrice when I find a cheaper buy price. This works in O(n) time and uses O(1) auxiliary space.

We are given stock prices for different days. We may buy the stock once and sell it once on a later day. We want the largest possible profit. If no positive profit is possible, the answer is 0. The main idea is to remember the cheapest earlier price while moving from left to right. Then each current day can be tested as a possible selling day. This avoids checking every possible pair of days and gives a simple one-pass solution.

1. Should I return only the maximum profit, not the buy and sell indices?
2. If no profitable transaction exists, should I return 0?
3. Can the input be empty or contain only one price?

The input is an integer array called prices. prices[i] is the stock price on day i. We may buy on one day and sell on a later day. We return the maximum profit from one transaction. We do not return the buy and sell indices. If no positive profit is possible, we return 0.

For the example prices = [7, 1, 5, 3, 6, 4], the answer is

5. We buy at index 1 for price 1 and sell at index 4 for price
6. The profit is 6 - 1 = 5.

I use a single left-to-right pass. I keep two integer variables. minPrice stores the lowest price seen on an earlier processed day. maxProfit stores the best valid buy-then-sell profit found so far.

The important invariant is this: before processing index i, minPrice is the lowest price seen on earlier processed days, and maxProfit is the best valid profit found so far.

If prices is null or has fewer than two elements, there is no possible buy followed by a later sell, so the method returns 0.

Otherwise, minPrice starts as prices[0], which is 7 in the example. maxProfit starts as 0. Traversal begins at index 1 because index 0 has already been used to initialize minPrice.

At index 1, the price is 1. Before this step, minPrice = 7 and maxProfit = 0. We calculate currentProfit = 1 - 7 = -6. Since -6 is not greater than 0, maxProfit stays 0. Because 1 is less than 7, minPrice becomes 1. After the step, minPrice = 1 and maxProfit = 0.

At index 2, the price is 5. Before the step, minPrice = 1 and maxProfit = 0. We calculate currentProfit = 5 - 1 = 4. Since 4 is greater than 0, maxProfit becomes 4. minPrice stays 1. After the step, minPrice = 1 and maxProfit = 4.

At index 3, the price is 3. Before the step, minPrice = 1 and maxProfit = 4. We calculate currentProfit = 3 - 1 = 2. Since 2 is not greater than 4, maxProfit stays 4. The price 3 is not less than minPrice, so minPrice stays 1. After the step, minPrice = 1 and maxProfit = 4.

At index 4, the price is 6. Before the step, minPrice = 1 and maxProfit = 4. We calculate currentProfit = 6 - 1 = 5. Since 5 is greater than 4, maxProfit becomes 5. minPrice stays 1. After the step, minPrice = 1 and maxProfit = 5.

At index 5, the price is 4. Before the step, minPrice = 1 and maxProfit = 5. We calculate currentProfit = 4 - 1 = 3. Since 3 is not greater than 5, maxProfit stays 5. The price 4 is not less than minPrice, so minPrice stays 1. After the step, minPrice = 1 and maxProfit = 5.

The loop is now complete, so the method returns 5.

When we calculate the profit for a selling day, minPrice represents the cheapest price from an earlier day. Therefore, every profit we compare represents a valid buy first and sell later transaction. We treat each later day as a possible selling day and keep the largest profit. When the loop finishes, maxProfit is therefore the best single-transaction profit.

The Java method first handles null input and arrays with fewer than two prices. It initializes minPrice with the first price and maxProfit with

1. The for loop starts at index
2. For each current price, it first calculates currentProfit using the existing minPrice. It updates maxProfit if that profit is better. It then updates minPrice if the current price is cheaper, so that lower price can be used by future selling days. Finally, it returns maxProfit.

The time complexity is O(n) because the algorithm examines each price at most once. The auxiliary space complexity is O(1) because it uses only a few integer variables. Important edge cases are an empty array, one element, strictly decreasing prices, duplicate prices, and a price of 0.

The key insight is that when we consider a day as a possible selling day, we only need the cheapest price that appeared before it. The algorithm stores that value in minPrice. It moves from left to right and calculates currentProfit = prices[i] - minPrice. If currentProfit is larger than maxProfit, it saves the new best profit. After checking the profit, it updates minPrice if the current price is cheaper. The central invariant is that before processing index i, minPrice is the cheapest earlier price and maxProfit is the best valid profit found so far. This avoids the O(n^2) approach of checking every pair of days.

The time complexity is O(n). We move through the array from left to right and examine each price at most once. For n prices, the work grows directly with n. The auxiliary space complexity is O(1). Auxiliary space means extra memory used by the algorithm. We only store minPrice, maxProfit, currentProfit, and the loop index, so the amount of extra memory does not grow with the number of prices.

A common mistake is solving the multiple-transactions version instead of allowing only one buy and one later sell. Another mistake is checking every pair of days with two nested loops, which takes O(n^2) time. Candidates can also mix up values and indices when explaining the example: index 1 has price 1, and index 4 has price 6. Another mistake is returning a negative profit for decreasing prices instead of 0. Finally, candidates may calculate the profit from the wrong state instead of using the cheapest earlier price.

State the invariant before writing the loop: before each index, minPrice is the cheapest earlier buy price and maxProfit is the best profit found so far. Then trace [7, 1, 5, 3, 6, 4] to show that the final profit becomes 5.

I would use the first string as the reference and compare one character position at a time across all the other strings. I move from left to right. If another string ends at the current position or has a different character, I return the part of the reference before that index. Otherwise, I continue. This works because every earlier checked position matches in all strings. The time complexity is O(S), where S is the characters compared, and auxiliary space is O(1).

We are given an array of strings and need to find the longest text that appears at the very beginning of every string. The matching characters must start at the first character and stay continuous. I use the first string as a reference and compare one position at a time with every other string. As soon as one string ends or has a different character, the shared beginning must stop there. This method directly follows the definition of a common prefix, can stop early, and does not need an extra data structure.

1. Can the input array be null or empty?
2. Can one of the strings be empty?
3. Should character comparison use the strings exactly as provided, including letter case?

The input is an array of strings. We must return the longest prefix shared by every string. A prefix starts at index 0 and contains continuous characters. For the diagram example, the input is ["flower", "flow", "flight"], and the expected output is "fl".

I use vertical scanning. The first string, "flower", is the reference. I compare its character at index i with the character at the same index in every remaining string. No extra collection is needed.

The central invariant is: before checking position i, every position before i already matches in all strings.

The reference is "flower". There are three strings. Processing starts at i = 0. For each reference position, the inner loop checks "flow" and then "flight" at that same position.

At i = 0, currentChar is 'f'. flow[0] is 'f' and flight[0] is 'f'. All strings match, so processing continues.

At i = 1, currentChar is 'l'. flow[1] is 'l' and flight[1] is 'l'. All strings still match, so the common prefix so far is "fl".

At i = 2, currentChar is 'o'. flow[2] is 'o', but flight[2] is 'i'. The condition detects a mismatch in "flight". Processing stops immediately. The method returns reference.substring(0, 2), which is "fl". Indices after 2 are not processed.

Before index i is checked, reference[0..i-1] is already known to match every string. Therefore, the first mismatch or the first point where another string ends is exactly where the common prefix must stop. Returning the substring before that position gives the longest possible common prefix.

The method first handles a null or empty input array by returning "". It stores strs[0] as reference. The outer loop visits reference from left to right. The inner loop checks the same index in every other string. It first checks whether that string ends at the current position. It also checks whether its character differs from currentChar. Either condition causes an immediate return. If every character in reference matches, the method returns the entire reference.

The time complexity is O(S), where S is the total number of characters compared across the strings. The algorithm can stop before examining all available characters. Auxiliary space is O(1), excluding the returned substring. The relevant edge cases are an empty array, one input string, no common prefix, and a shorter string that limits the possible prefix.

Use vertical scanning with the first string as the reference. For each index i in the reference, read currentChar and compare it with the character at index i in every remaining string. If another string has length i, that string has ended and the prefix cannot continue. If its character is different, the prefix also cannot continue. In either case, return reference.substring(0, i). The invariant is that before index i is checked, reference[0..i-1] matches every string. Because of that invariant, the first failure position is exactly the boundary of the longest common prefix.

Time is O(S), where S is the total number of characters compared across the strings. The algorithm compares characters only until it finds a mismatch or reaches the end of a shorter string, so it can stop early. In the diagram example, it processes indices 0, 1, and 2 and stops at the mismatch at index 2. Auxiliary space is O(1) because only the reference, loop indices, and current character are stored. This excludes memory used by the returned substring.

One mistake is reading strs[j].charAt(i) before checking whether that string has already ended. That can cause an index error. Another mistake is continuing after the first mismatch instead of returning immediately. Candidates may also compare different positions between strings, which does not test a common prefix. Another common error is confusing a prefix with a subsequence. A prefix must start at index 0 and remain continuous. Finally, do not claim a simpler O(n) bound without defining n. For this implementation, O(S) describes the total characters compared.

State the invariant before writing the loops: every position before i already matches in all strings. Then the early return is easy to explain because the first mismatch or string end is exactly the prefix boundary.

I would use an in-place two-pointer approach. I keep insertPos at the next position where a non-zero value should go, while current scans the array from left to right. When current finds a non-zero value, I swap it with nums[insertPos] and then move insertPos forward. Zeroes are skipped. This preserves the relative order of the non-zero values and moves all zeroes to the end. The time complexity is O(n), and the auxiliary space complexity is O(1).

The input is an integer array. The goal is to change that same array so every zero is at the end. The non-zero numbers must stay in the same relative order as before. For example, [0, 1, 0, 3, 12] must become [1, 3, 12, 0, 0]. We can do this without creating another array. We keep one position for where the next non-zero number belongs. Then we read the array from left to right and move each non-zero number into that position.

1. Should I modify the input array in place?
2. Must the relative order of the non-zero values stay unchanged?
3. Can the input array be empty?

We receive an integer array and modify it in place. The result is the same array with every zero moved to the end. The non-zero values must keep their original relative order. For the example [0, 1, 0, 3, 12], the final array is [1, 3, 12, 0, 0].

I use two integer positions. current scans every array position from left to right. insertPos tells me where the next non-zero value should be placed. The important invariant is that, before each step, indices from 0 through insertPos - 1 contain exactly the non-zero values seen so far in their original order.

The array starts as [0, 1, 0, 3, 12]. I set insertPos = 0 because no non-zero values have been placed yet. The traversal starts with current = 0.

At current = 0, the value is 0. The condition nums[current] != 0 is false, so I skip it. The array stays [0, 1, 0, 3, 12], and insertPos stays 0.

At current = 1, the value is 1. It is non-zero, so I swap nums[0] and nums[1]. The array changes from [0, 1, 0, 3, 12] to [1, 0, 0, 3, 12]. Then insertPos becomes 1.

At current = 2, the value is 0. I skip it. The array stays [1, 0, 0, 3, 12], and insertPos stays 1.

At current = 3, the value is 3. It is non-zero, so I swap nums[1] and nums[3]. The array changes from [1, 0, 0, 3, 12] to [1, 3, 0, 0, 12]. Then insertPos becomes 2.

At current = 4, the value is 12. It is non-zero, so I swap nums[2] and nums[4]. The array changes from [1, 3, 0, 0, 12] to [1, 3, 12, 0, 0]. Then insertPos becomes 3. current has now reached the end of the array, so the traversal stops.

Each non-zero value is placed into the next open position from the left. Because current moves only from left to right, those non-zero values are placed in the same order in which they originally appear. Zeroes are skipped. As non-zero values are swapped left, zeroes move toward the right. When the traversal finishes, the front contains the non-zero values in their original order and the remaining positions contain zeroes.

The Java loop visits each index from 0 to nums.length - 1. It performs a swap only when nums[current] is non-zero, then increments insertPos. The method returns nothing because it modifies nums directly. The algorithm takes O(n) time and O(1) auxiliary space. The same loop handles an empty array, a one-element array, an array containing only zeroes, an already compact array with no zeroes, and arrays with zeroes at the front, middle, or end.

The key idea is stable in-place compaction using two positions. insertPos marks the next index where a processed non-zero value belongs. current scans from left to right. If nums[current] is zero, the algorithm skips it. If nums[current] is non-zero, that value is swapped into nums[insertPos], and insertPos advances by one. The central invariant is that indices [0 .. insertPos - 1] always contain exactly the non-zero values processed so far, in their original relative order. This gives the required ordering without using another array.

Let n be the number of elements in the array. The time complexity is O(n) because current moves from index 0 to index n - 1 and processes every array position once. Each condition check and swap takes constant time. The auxiliary space complexity is O(1) because the algorithm uses only insertPos, current, and one temporary value for swapping. It does not allocate another array or another data structure whose size grows with n.

1. Using a second array even though this problem can be solved with O(1) auxiliary space.
2. Reordering the non-zero values instead of preserving their original relative order.
3. Incrementing insertPos when nums[current] is zero. insertPos should advance only after placing a non-zero value.
4. Writing only one side of the swap and losing the value that was previously stored at insertPos.
5. Claiming O(1) auxiliary space while using an extra array whose size grows with the input.

State the invariant before you code: everything before insertPos is already the processed non-zero prefix in the correct relative order. Then trace [0, 1, 0, 3, 12] and show that insertPos moves only after a non-zero value is placed.

I would use a stack to keep the opening brackets that have not been matched yet. I read the string from left to right. I push each opening bracket. For a closing bracket, I first check that the stack is not empty, then pop the top and verify that the bracket types match. This also enforces the correct nesting order. At the end, the stack must be empty. The time complexity is O(n), and the auxiliary space is O(n).

The input is a string made only of parentheses, square brackets, and curly brackets. We need to return true only when every opening bracket has the correct closing bracket and the brackets close in the correct order. A stack fits this problem because the most recently opened bracket must be closed first. We move from left to right, store opening brackets, and compare each closing bracket with the top of the stack. The example in the diagram is s = "([{}])", which returns true.

1. Should an empty string be considered valid and return true?
2. Can I assume the input contains only '(', ')', '[', ']', '{', and '}' as stated?

The input is one string. Every character is one of the six bracket characters. We return a boolean value. We return true only if every opening bracket has a matching closing bracket of the same type and the nesting order is correct.

For the example s = "([{}])", the characters and indices are: 0 -> '(' 1 -> '[' 2 -> '{' 3 -> '}' 4 -> ']' 5 -> ')'

The expected result is true.

I use a stack. Each stack entry is an opening bracket that has been seen but not matched yet. The top of the stack is the most recent unmatched opening bracket.

The central invariant is: the stack always contains exactly the unmatched opening brackets seen so far, in nesting order. Therefore, when a closing bracket appears, it must match the current top.

Start with an empty stack: []. Begin at index 0 and move from left to right.

If the current character is '(', '[', or '{', push it onto the stack. If it is a closing bracket, first check whether the stack is empty. An empty stack means there is no opening bracket available to match, so return false. Otherwise, pop the top opening bracket and compare the types. Return false immediately if they do not match.

Step 1: i = 0, ch = '('. The stack is []. This is an opening bracket, so push it. The stack becomes ['(']. Continue.

Step 2: i = 1, ch = '['. The stack is ['(']. Push '['. The stack becomes ['(', '[']. Continue.

Step 3: i = 2, ch = '{'. The stack is ['(', '[']. Push '{'. The stack becomes ['(', '[', '{']. Continue.

Step 4: i = 3, ch = '}'. The stack is ['(', '[', '{']. The top is '{', which matches '}'. Pop it. The stack becomes ['(', '[']. Continue.

Step 5: i = 4, ch = ']'. The stack is ['(', '[']. The top is '[', which matches ']'. Pop it. The stack becomes ['(']. Continue.

Step 6: i = 5, ch = ')'. The stack is ['(']. The top is '(', which matches ')'. Pop it. The stack becomes []. Continue.

All 6 characters have now been processed. The stack is empty, so return true.

Every opening bracket is pushed when it appears. A closing bracket can succeed only when it matches the most recent unmatched opening bracket at the top of the stack. This checks both bracket type and nesting order. If all comparisons succeed and no unmatched opening bracket remains at the end, the whole string is balanced. For "([{}])", every closing bracket matches correctly and the final stack is empty, so the returned value is true.

The Java code uses Deque<Character> with ArrayDeque as the stack. stack.push(ch) adds an opening bracket to the top. Before processing a closing bracket, stack.isEmpty() prevents an invalid pop. stack.pop() removes the opening bracket that must be matched next. Three direct comparisons check (), [], and {}. Any mismatch returns false immediately. After the loop, stack.isEmpty() is returned so unmatched opening brackets also make the result false.

Let n be the number of characters. Each character is processed at most once. Each stack push or pop is O(1), so the total time is O(n). The stack can contain up to n opening brackets, so auxiliary space is O(n).

Important edge cases from the diagram are: an empty string returns true, "(" returns false, ")" returns false, "([)]" returns false because the nesting order is wrong, and "()[]{}" returns true.

The key idea is that valid brackets close in the reverse order in which they open. A stack directly represents this rule. Each opening bracket is pushed onto the stack. For every closing bracket, the algorithm checks the most recent unmatched opening bracket at the top. If the stack is empty or the types do not match, the string is invalid immediately. The invariant is that the stack contains exactly the unmatched opening brackets seen so far, with the newest one on top. After processing the whole string, an empty stack means every opening bracket was matched correctly.

Let n be the number of characters in the string. The time complexity is O(n) because we process each character at most once. Each push and pop on ArrayDeque takes constant time. The auxiliary space is O(n) because, in the worst case, the string can contain only opening brackets and all of them must remain in the stack. Auxiliary space means the extra memory used by the algorithm.

A common mistake is checking only how many opening and closing brackets exist. That does not detect wrong nesting such as "([)]". Another mistake is popping before checking whether the stack is empty. Candidates may also forget to compare the bracket types, so a ')' could incorrectly match '[' or '{'. Another mistake is forgetting the final stack-empty check, which would incorrectly accept a string such as "(". The stack must always use LIFO order so the newest unmatched opening bracket is checked first.

State the stack invariant before coding: the stack contains the unmatched opening brackets, and its top is the opening bracket that the next closing bracket must match.

I would sort the array first, then fix one number as an anchor and use two pointers on the remaining sorted part. If the sum is too small, I move the left pointer right. If it is too large, I move the right pointer left. When the sum is zero, I save the triplet and skip duplicate values. This finds all unique triplets in O(n^2) time, with O(log n) auxiliary space from Java's primitive array sort.

The input is an integer array, and the goal is to return every different group of three values whose sum is zero. The same triplet must not appear more than once. I first sort the numbers. Then I choose one number as an anchor and search the remaining part with a left and right pointer. Sorting makes pointer movement predictable. It also makes duplicate values easy to skip. For the example [-1, 0, 1, 2, -1, -4], the result is [[-1, -1, 2], [-1, 0, 1]].

1. Should the returned triplets contain values rather than original indices?
2. Can the input contain duplicate, negative, and zero values?
3. Is modifying the input by sorting acceptable?

We receive an integer array and return unique triplets of values. We are not returning original indices. For the diagram example, the input is [-1, 0, 1, 2, -1, -4]. One valid returned result is [[-1, -1, 2], [-1, 0, 1]]. Each triplet sums to zero, and duplicate triplets are removed.

I sort the array in ascending order. The sorted values are [-4, -1, -1, 0, 1, 2]. For each anchor nums[i], I place left at i + 1 and right at the last index. The important invariant is that, for a fixed anchor, left and right scan the remaining sorted suffix. Moving left increases the sum. Moving right decreases the sum. This lets us find the needed pairs efficiently for each anchor.

The result list starts empty. Traversal begins at i = 0. For each distinct anchor, left starts one position after the anchor and right starts at the end. If i > 0 and nums[i] equals nums[i - 1], I skip that anchor because it would repeat triplets already found. If nums[i] is positive, I stop the outer loop because every later value is also positive, so three values can no longer sum to zero.

After sorting, the array is [-4, -1, -1, 0, 1, 2].

For i = 0, the anchor is -4. left = 1 and right = 5. The sum is -4 + -1 + 2 = -3, so I move left rightward. At left = 2, the sum is again -3. At left = 3, the sum is -2. At left = 4, the sum is -1. Each sum is too small, so left keeps moving right. No zero-sum pair exists for anchor -4.

For i = 1, the anchor is -1. left = 2 and right = 5. The sum is -1 + -1 + 2 = 0, so I add [-1, -1, 2]. Then I move both pointers inward. Now left = 3 and right = 4. The sum is -1 + 0 + 1 = 0, so I add [-1, 0, 1]. Moving both pointers inward ends this anchor's search.

At i = 2, nums[2] is -1 and equals nums[1], so I skip this duplicate anchor. At i = 3, the anchor is 0. left = 4 and right = 5. The sum is 0 + 1 + 2 = 3, so I move right leftward. left and right then meet, so the search ends. The final result is [[-1, -1, 2], [-1, 0, 1]].

For each distinct anchor, the remaining values are sorted. If the current sum is too small, moving left is safe because moving to a larger left value is the only pointer move that can increase the sum. If the current sum is too large, moving right is safe because moving to a smaller right value decreases the sum. When the sum is zero, we record the triplet. Skipping repeated anchors and repeated neighboring pointer values prevents duplicate triplets without removing a new unique result.

The code sorts nums first. The outer loop chooses each distinct anchor. It stops when the anchor becomes positive. For each anchor, a while loop runs while left < right. It calculates nums[i] + nums[left] + nums[right]. A zero sum is added to the result. Both pointers then move inward, and repeated neighboring values are skipped. A negative sum moves left. A positive sum moves right. Finally, the method returns every unique triplet found.

Sorting takes O(n log n). The outer loop combined with the two-pointer scan takes O(n^2), so the total time is O(n^2). Under the diagram's Java primitive-array sorting model, the auxiliary space is O(log n), excluding the returned output. Important cases are arrays with fewer than three values, [0, 0, 0], repeated numbers, and arrays containing only positive or only negative values.

The key idea is to sort first and then turn each anchor position into a two-pointer search. For a fixed nums[i], left begins at i + 1 and right begins at n - 1. The central invariant is that left and right remain inside the sorted suffix to the right of the anchor. If the sum is below zero, moving left rightward increases the sum. If the sum is above zero, moving right leftward decreases the sum. When the sum is zero, the triplet is recorded. Duplicate anchors and duplicate neighboring pointer values are skipped so each value triplet appears only once.

Let n be the number of values. Sorting costs O(n log n). For each anchor, the left and right pointers move inward through the remaining suffix, so the total two-pointer work across all anchors is O(n^2). O(n^2) dominates O(n log n), so the total time is O(n^2). Under the diagram's Java primitive-array sorting model, sorting uses O(log n) auxiliary stack space. The two-pointer search itself uses only a few variables. The returned list is output space and is excluded from that auxiliary-space figure.

A common mistake is forgetting to sort before using the pointer movement rules. Another is moving the wrong pointer: when the sum is negative, left must move rightward, and when the sum is positive, right must move leftward. Candidates also often forget to skip a repeated anchor such as the second -1. After recording a valid triplet, repeated left and right values must be skipped too. Another mistake is returning original indices instead of the triplet values required here. Finally, sorting cost and sorting stack space should be included in the complexity discussion.

Explain the pointer rule before writing the loop: after sorting, a sum below zero means move left, a sum above zero means move right, and a zero sum means record the triplet, move both pointers inward, and skip duplicates. That one rule makes both the code and the correctness argument easier to follow.

I would add the two linked lists one digit at a time while carrying any overflow to the next position. I keep two pointers, one for each list, plus a dummy head for the result and an integer carry. At each step, I add the two current values and the carry, append sum % 10, and update the carry with sum / 10. I continue until both lists and the carry are finished. The time is O(max(m, n)), with O(1) auxiliary space excluding the returned list.

Each list stores one digit in each node. The digits are in reverse order, so the first nodes represent the ones place. We need to add the two numbers and build a new list in the same order. I add matching digit positions together and keep any carry for the next position. This fits the input well because we can move through both lists from the beginning. We do not need to reverse the lists or convert them into normal integer values.

1. Are the digits stored in reverse order, with the ones digit first?
2. Should I return a new linked list instead of changing the input lists?
3. Can the two lists have different lengths?

The input is two linked lists. Each node contains one digit. The digits are stored in reverse order. For example, 2 -> 4 -> 3 represents 342, and 5 -> 6 -> 4 represents 465. We must return a new linked list containing the sum in the same reverse order. For this example, 342 + 465 = 807, so the result is 7 -> 0 -> 8, or [7, 0, 8].

I use two pointers, p1 and p2, to walk through the input lists together. I also keep an integer carry. A dummy node starts the result list, and tail always points to its last node. Reverse-order storage is useful because the first nodes are the least significant digits, which is exactly where normal addition starts.

The central invariant is: dummy.next contains the correct result digits for every position already processed, and carry contains the overflow that must be added to the next digit position.

Set p1 = l1 and p2 = l2. Create dummy = new ListNode(0) and set tail = dummy. Set carry = 0. At this point, the result is empty because dummy.next is null. Traversal begins at values 2 and 5 in the example.

Step 1 starts with p1.val = 2, p2.val = 5, and carry = 0. The calculation is 2 + 5 + 0 = 7. The new digit is 7 % 10 = 7, and the new carry is 7 / 10 = 0. Append node 7. The result is now 7. Move both pointers forward.

Step 2 uses values 4 and 6 with carry 0. The calculation is 4 + 6 + 0 = 10. The digit is 10 % 10 = 0, and the carry becomes 10 / 10 = 1. Append node 0. The result is now 7 -> 0. Move both pointers forward.

Step 3 uses values 3 and 4 with carry 1. The calculation is 3 + 4 + 1 = 8. The digit is 8 % 10 = 8, and the carry becomes 8 / 10 = 0. Append node 8. The result is 7 -> 0 -> 8. Both pointers are now null and carry is 0, so the loop stops. All three digit positions have been processed.

Each loop iteration performs normal addition for exactly one digit position. sum % 10 gives the digit that belongs in the current position. sum / 10 keeps any overflow for the next position. Since both pointers advance one node at a time when possible, every position is processed in order. When both lists are finished and carry is 0, all required positions have been handled, so dummy.next is the correct sum list.

The loop continues while p1 has a node, p2 has a node, or carry is not zero. If one list ends first, its missing digit is treated as 0. After calculating the new digit and carry, the code creates one new result node and moves tail. It then advances each input pointer when that pointer is not null. Finally, it returns dummy.next, which skips the temporary dummy node.

If the list lengths are m and n, the time is O(max(m, n)) because each input node is processed at most once, with at most one extra iteration for a final carry. The algorithm uses O(1) auxiliary space because it keeps only a few pointers and integer variables. The returned list itself can contain O(max(m, n) + 1) nodes. Important edge cases are different list lengths, a final carry such as 9 -> 9 plus 1, zero values, and single-node lists.

The key idea is to perform normal elementary addition directly on the linked lists. Because the digits are stored in reverse order, traversal already starts at the ones place. Two pointers read the current digits. If one pointer has reached the end, its digit is treated as 0. The algorithm adds both digits and the incoming carry, appends sum % 10, and keeps sum / 10 as the next carry. A dummy head makes result construction simple. The invariant is that dummy.next always contains the correct digits for all processed positions, while carry stores the overflow for the next position.

Let m be the number of nodes in the first list and n be the number of nodes in the second list. The time complexity is O(max(m, n)) because each input node is processed at most once, and there can be at most one additional iteration for a final carry. The auxiliary space is O(1) because the algorithm only keeps a few pointers and integer variables. This does not count the returned linked list. The output list can contain up to O(max(m, n) + 1) nodes because a final carry may create one extra node.

A common mistake is forgetting the carry after a sum such as 4 + 6 = 10. Another mistake is stopping when both input pointers become null even though a final carry may remain. Candidates may also forget to use 0 after one list ends, which breaks different-length inputs. Another mistake is advancing a pointer without checking whether it is null. Finally, returning dummy instead of dummy.next incorrectly includes the temporary zero node in the result.

While coding, say the invariant out loud: the result list already contains the correct digits for every processed position, and carry is the overflow that belongs to the next position. This makes the loop condition, digit calculation, and stopping condition easy to justify.