460 Python Developer Interview Questions & Answers

I would use two pointers. One starts at the beginning of the string, and the other starts at the end. First, I convert the string to lowercase so letter case does not affect the comparison. While left is before right, I compare the mirrored characters. If they differ, I return False immediately. Otherwise, I move both pointers inward. If the loop finishes, I return True. The time complexity is O(n). The complete Python implementation uses O(n) auxiliary space because lower() creates a new string.

The problem asks us to decide whether a string reads the same forward and backward. The solution uses two pointers. One pointer starts at the first character, and the other starts at the last character. Before comparing them, the code converts the string to lowercase. This makes the check case-insensitive, so "Level" is treated as "level".

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is one string. The function returns True when the string is a palindrome. It returns False when at least one pair of mirrored characters is different.

The solution treats uppercase and lowercase versions of the same letter as equal. For example, the input "Level" becomes "level" before the comparisons begin.

We use two integer pointers named left and right.

The left pointer starts at index 0. The right pointer starts at the last index, which is len(text) - 1.

The central invariant is that every mirrored pair outside the current left and right positions has already matched. When the current pair also matches, both pointers can safely move toward the center.

For the example input "Level", the normalized string is "level".

Its length is 5. The indices are 0, 1, 2, 3, and 4.

The characters are:

index 0 = "l" index 1 = "e" index 2 = "v" index 3 = "e" index 4 = "l"

We start with left = 0 and right = 4.

At step 1, the state is left = 0 and right = 4.

We compare text[0], which is "l", with text[4], which is also "l". The characters are equal. We move both pointers inward. The new state is left = 1 and right = 3.

At step 2, we compare text[1], which is "e", with text[3], which is also "e". The characters are equal. We move both pointers inward again. The new state is left = 2 and right = 2.

The loop condition is left < right. At this point, 2 < 2 is false, so the loop stops. The middle character does not need to be compared with itself.

No mismatch was found, so the function returns True.

A palindrome must have equal characters at mirrored positions. The first character must match the last character. The second character must match the second-last character, and so on.

If one mirrored pair is different, the string cannot read the same in both directions. Returning False immediately is therefore correct.

If every required mirrored pair matches until the pointers meet or cross, the whole string is a palindrome. Returning True is therefore correct.

The function first calls s.lower() and stores the new lowercase string in text.

It initializes left to 0 and right to len(text) - 1.

The while loop runs while left < right. Inside the loop, the code compares text[left] and text[right]. If they are different, it returns False immediately.

If they match, left increases by 1 and right decreases by 1. When the loop finishes without a mismatch, the function returns True.

The time complexity is O(n), where n is the string length. In the worst case, the algorithm checks all mirrored pairs until the pointers reach the center. The lowercase conversion also takes O(n) time.

The pointer logic itself uses O(1) extra space. However, the complete Python implementation uses O(n) auxiliary space because s.lower() creates a new string.

An empty string returns True because left starts at 0 and right starts at -1, so the loop never runs.

A one-character string returns True because left and right both point to index 0, so the loop never runs.

Different letter cases are handled by converting the input to lowercase.

A string such as "abc" returns False at the first comparison because "a" and "c" do not match.

The key insight is that a palindrome can be verified by comparing characters in mirrored positions. A two-pointer approach does this directly. The left pointer begins at the start, and the right pointer begins at the end. The invariant is that every mirrored pair outside the two pointers has already matched. If the current pair differs, the answer is False. If it matches, both pointers move inward. When the pointers meet or cross, every required pair has matched, so the answer is True. This avoids creating a reversed copy only for comparison, although the shown implementation still creates a lowercase copy for case-insensitive checking.

Let n be the number of characters in the input string. Calling lower() takes O(n) time. The two pointers then compare at most about half of the character pairs, which is also O(n) time. Therefore, the total time complexity is O(n). The two pointer variables use O(1) extra space. However, Python creates a new string when lower() is called, so the complete implementation uses O(n) auxiliary space. If the input were already normalized and no copy were created, the pointer algorithm alone would use O(1) auxiliary space.

One mistake is comparing the original characters without normalizing letter case, which makes "Level" incorrectly return False. Another mistake is moving only one pointer or moving a pointer in the wrong direction. A candidate may also forget to return False immediately when a mismatch is found. Another common error is placing return True inside the loop, which may return before all mirrored pairs have been checked. It is also incorrect to claim that the complete shown implementation uses O(1) auxiliary space, because lower() creates a new string of length n.

Explain the invariant before writing the loop: every mirrored pair outside left and right has already matched. Then show that a mismatch returns False and a match moves both pointers inward.

I would process the list from left to right and keep a set called seen. For each string, I check whether it is already in the set. If it is new, I print it and add it to seen. If it is already present, I skip it. This keeps the order of first appearance because I traverse the original list. The solution takes O(n) expected time and O(k) auxiliary space, where k is the number of distinct strings.

The problem asks us to print every distinct string once, even when the input contains duplicates. A set is a good fit because it can quickly tell us whether a string has already been printed. We still process the original list from left to right, so the printed values keep their first-appearance order.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is a list of strings. Some strings may appear more than once.

For this example:

["apple", "banana", "apple", "orange", "banana", "grape"]

The printed output is:

apple banana orange grape

We print the string values themselves. We do not return indices or build a separate result list.

We use a set named seen. The set stores every string that has already been printed.

The central invariant is simple: before each iteration, seen contains exactly the distinct strings printed during earlier iterations.

We do not rely on the set to define the output order. We traverse the original list from left to right, and the set is used only to check whether a value has appeared before.

At the beginning, the set is empty:

seen = set()

Nothing has been printed yet. Processing starts with the first string in the list.

Step 1 processes "apple". The set is empty, so "apple" is not in seen. We print "apple" and add it to the set. The set becomes {"apple"}.

Step 2 processes "banana". It is not in seen. We print it and add it. The set becomes {"apple", "banana"}.

Step 3 processes "apple" again. It is already in seen, so we skip it. The set and printed output stay unchanged.

Step 4 processes "orange". It is not in seen. We print it and add it. The set now contains "apple", "banana", and "orange".

Step 5 processes "banana" again. It is already in seen, so we skip it.

Step 6 processes "grape". It is not in seen. We print it and add it. The set now contains all four distinct strings.

Processing stops after the final element. The printed output is apple, banana, orange, and grape.

A string is printed only when it is not already in seen. Immediately after printing a new string, we add it to seen. Therefore, the same string cannot be printed again later.

Because we process the original list from left to right, each distinct string is printed at its first occurrence. This preserves the order of first appearance.

The function creates an empty set and loops through each string in the input.

The condition string not in seen checks whether the current string has already been printed. When the string is new, the function prints it and adds it to the set. Repeated strings fail the condition and are skipped.

The function prints the values directly. It returns None because no separate result list is required.

Let n be the total number of input strings. Each string is processed once. Python set lookup and insertion take O(1) time on average, so the total expected time is O(n).

Let k be the number of distinct strings. The set stores those k strings, so the auxiliary space is O(k). In the worst case, every string is distinct and k equals n.

An empty list prints nothing. If all strings are identical, only the first one is printed. If all strings are unique, every string is printed in the original order. String comparison is case-sensitive, so "Apple" and "apple" are treated as different values.

The key idea is to separate traversal order from duplicate detection. We traverse the original list from left to right so the first-appearance order is preserved. A set named seen remembers which strings have already been printed. Before each iteration, seen contains exactly the distinct strings printed from earlier positions. If the current string is not in seen, we print it and add it. Otherwise, we skip it. This avoids repeatedly searching through the earlier part of the list.

Let n be the total number of strings and k be the number of distinct strings. We examine every input string once. A Python set lookup and insertion take O(1) time on average, so the total expected time is O(n). The set stores up to k distinct strings, so the auxiliary space is O(k). If every string is different, k equals n. The O(n) time is expected time because hash-set operations are average O(1), not guaranteed O(1) in every worst-case situation.

One mistake is converting the list directly to a set and printing the set. That removes duplicates, but it does not clearly preserve the order of first appearance. Another mistake is forgetting to add a printed string to seen, which allows later duplicates to be printed. A candidate may also add the string before checking membership, causing every value to appear already seen. Using a list instead of a set for membership checks can make the solution O(n²). It is also incorrect to describe the hash-based running time as guaranteed O(n) instead of expected O(n).

State the invariant clearly: before each iteration, seen contains exactly the strings already printed. Then explain that traversing the original list preserves first-appearance order while the set prevents duplicate output.

I solve this by recursion. If the string has zero or one character, I return it because it is already reversed. Otherwise, I recursively reverse everything after the first character, then append the first character to the returned string. For "code", the return path builds "e", "ed", "edo", and finally "edoc". For this exact Python implementation, the time complexity is O(n²), and the auxiliary space complexity is O(n²) because slicing and concatenation create new strings.

The problem asks us to reverse a string by using recursion. The idea is to reduce the problem by one character in each call. We save the first character, recursively reverse the remaining substring, and append the saved character while the calls return. This gives the exact result shown in the diagram.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is a string named s. The function must return a new string containing the same characters in reverse order.

For the example:

Input: "code"

Output: "edoc"

The function returns characters in reversed order. It does not return indices or modify the original string.

The base case is:

If len(s) <= 1, return s.

An empty string and a one-character string are already reversed, so recursion can stop.

For a longer string, the rule is:

reverse(s) = reverse(s[1:]) + s[0]

The expression s[1:] is the substring after the first character. The expression s[0] is the first character. The function first reverses the smaller substring. It then adds the saved first character to the end.

The first call is reverse_string("code"). Its length is 4, so it calls reverse_string("ode") and waits to append 'c'.

The second call is reverse_string("ode"). Its length is 3, so it calls reverse_string("de") and waits to append 'o'.

The third call is reverse_string("de"). Its length is 2, so it calls reverse_string("e") and waits to append 'd'.

The fourth call is reverse_string("e"). Its length is 1, so the base case returns "e" immediately.

The recursive inputs are therefore:

"code" -> "ode" -> "de" -> "e"

After the base case returns, the waiting calls continue in reverse order.

The call for "de" receives "e" and calculates "e" + "d". It returns "ed".

The call for "ode" receives "ed" and calculates "ed" + "o". It returns "edo".

The call for "code" receives "edo" and calculates "edo" + "c". It returns "edoc".

The exact return sequence is:

"e" -> "ed" -> "edo" -> "edoc"

The base case is correct because a string with zero or one character is already reversed.

For a longer string, assume the recursive call correctly reverses s[1:]. The original first character s[0] must appear after all the other characters in the reversed result. Appending s[0] to reverse(s[1:]) places it in exactly that position.

Therefore, reverse(s[1:]) + s[0] correctly reverses the full string.

The function receives s as a string and returns a string.

It first checks len(s) <= 1. If that condition is true, it returns s.

Otherwise, it creates the smaller substring s[1:] and passes it to the same function. When that call returns, the code adds s[0] to the end of the returned substring.

Python uses the recursion call stack to remember each waiting call. No hash map, queue, or explicit stack is created.

Let n be the length of the string.

The time complexity is O(n²) for this exact Python implementation. Each call creates a slice with s[1:]. Each return also creates a new string during concatenation. These operations repeatedly copy characters.

The auxiliary space complexity is O(n²) overall because the recursive calls retain copied substrings whose total size is quadratic. The recursion depth itself is O(n).

An empty string returns "". A one-character string such as "a" returns "a". Repeated characters work normally, so "aab" becomes "baa". Spaces and punctuation are also reversed as normal characters.

The key insight is to solve the same problem on a shorter string. Each call removes the first character and recursively reverses the remaining substring. The call stack remembers the removed characters. During the return path, each saved character is appended to the end of the smaller reversed result. The central invariant is: for every string s with length greater than one, reverse(s) equals reverse(s[1:]) plus s[0]. The base case handles strings of length zero or one.

Let n be the number of characters. The time complexity is O(n²) for this exact Python code. The slice s[1:] copies characters in every recursive call. The + operation also creates and copies a new string during every return. These repeated copies add up to quadratic work. The auxiliary space complexity is O(n²) overall because the calls retain copied substrings. The recursion stack has O(n) depth.

A common mistake is forgetting the base case. That causes recursion to continue until Python raises an error. Another mistake is writing s[0] + reverse_string(s[1:]), which keeps the original order instead of reversing it. Some candidates use a different slice but keep the same return logic, which makes the result incorrect. Another mistake is explaining the downward calls but not the return path. Candidates also often claim O(n) time or O(n) space without counting Python slicing, concatenation, and copied substrings.

Write the recursive rule first: reverse(s) = reverse(s[1:]) + s[0]. Then trace "code" down to "e" and back up to "edoc". This clearly shows both the base case and the return path.

I first split the sentence into a list of words. For the first output, I reverse the characters inside each word while keeping the words in their original positions. For the second output, I reverse the order of the original words without changing their characters. For "How are you", the results are "woH era uoy" and "you are How". The algorithm takes O(n) time and O(n) auxiliary space because it creates word data and new output strings.

The problem asks us to apply two different transformations to the same input sentence. One transformation reverses the characters inside each word. The other reverses the positions of the words. Splitting the sentence into words is a good fit because it lets us transform each word or change the list order without mixing the two operations.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is the string "How are you".

We need to produce two separate results.

For the first result, each word stays in its original position, but the characters inside the word are reversed.

"How" becomes "woH".

"are" becomes "era".

"you" becomes "uoy".

The first output is "woH era uoy".

For the second result, each word keeps its original characters, but the order of the words is reversed.

["How", "are", "you"] becomes ["you", "are", "How"].

The second output is "you are How".

We call split on the input string.

Before this step, the state is the string "How are you".

After this step, the state is the list ["How", "are", "you"].

This original word list is used to build both outputs.

We process the words from left to right.

The current word is "How". Reversing its characters gives "woH".

The current word is "are". Reversing its characters gives "era".

The current word is "you". Reversing its characters gives "uoy".

The transformed words are ["woH", "era", "uoy"].

We join them with one space between neighboring words. The first result is "woH era uoy".

We use the original list ["How", "are", "you"]. We do not use the character-reversed words from the first transformation.

Reversing the list order gives ["you", "are", "How"].

We join these words with spaces. The second result is "you are How".

For the first transformation, the algorithm applies character reversal independently to every word. It never changes the position of a word. Therefore, each output word is the reverse of the corresponding input word.

For the second transformation, the algorithm reads the original word list from the last position to the first position. It does not change the characters inside a word. Therefore, the output contains the original words in exactly reversed order.

The function calls text.split() to create the original word list. A generator expression applies word[::-1] to each word, and join builds the first output. The expression words[::-1] creates the words in reversed order, and another join builds the second output. The function returns both strings as a tuple.

Let n be the total number of characters in the input. Splitting the string, reversing all word characters, reversing the word list, and building the output strings together take O(n) time.

The auxiliary space complexity is O(n). The word list, reversed list slice, temporary reversed word strings, and returned strings grow with the input size.

For an empty string, both outputs are empty strings. For a one-word string, the first output reverses that word, while the second output is unchanged. Character case is preserved. Because the implementation uses split and joins with one space, repeated spaces or leading and trailing spaces are normalized in the outputs.

The key insight is that the two required results change different levels of the sentence. The first result changes characters inside each word. The second result changes the positions of whole words. We first create the original word list and then build both results independently from it. The first invariant is that every processed word remains at its original word position and has its characters reversed. The second invariant is that every output position receives the corresponding original word from the opposite end of the list.

Let n be the total number of characters in the input string. Splitting the sentence takes O(n) time. Reversing the characters across all words takes O(n) time because the total number of word characters is at most n. Reversing the word list and joining both outputs also take O(n) time. Therefore, the total time complexity is O(n). The auxiliary space complexity is O(n) because the code creates a word list, a reversed list slice, reversed word strings, and new result strings.

A common mistake is reversing the complete string, which produces "uoy era woH" and combines both transformations incorrectly. Another mistake is using the reversed-character words to build the second output instead of using the original word list. A candidate may also reverse the word order for the first output or reverse the characters for the second output. Another mistake is claiming O(1) auxiliary space even though Python creates new lists, slices, reversed strings, and result strings. It is also easy to forget that split normalizes repeated whitespace.

Show the original word list once, and then draw two separate branches from it. One branch reverses characters inside each word. The other branch reverses only the list order. This makes the difference between the two outputs clear.

I would solve this with a one pass hash map. The map stores each value I have already seen and its index. For each current value, I calculate the complement needed to reach the target. I check the map before storing the current value, so I cannot reuse the same element. When the complement is found, I return the earlier index and the current index. This takes O(n) expected time and O(n) auxiliary space.

The problem gives an integer array and a target. We must return the indices of two different elements whose values add up to the target. A one pass hash map works well because it lets us check whether the needed earlier value has already appeared.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is an integer array and a target value. The answer must contain two indices, not the two values themselves. The problem guarantees exactly one valid pair, and the two indices must refer to different elements.

I create an empty dictionary named seen. It stores each processed value as the key and that value's earlier index as the dictionary value. The important rule is that seen contains only elements that appeared before the current index.

For each value, I calculate complement = target - value. The complement is the number needed to complete the target. I check whether that complement is already in seen before storing the current value. This order prevents the same array element from being used twice.

The diagram uses nums = [2, 7, 11, 15] and target = 9. At index 0, the value is 2, so the complement is 7. The map is empty, so 7 is not found. I store 2: 0 in the map.

At index 1, the value is 7, so the complement is 2. The map contains 2: 0. Therefore, the earlier index is 0 and the current index is 1. I return [0, 1] and stop. The later elements are not processed.

Before each lookup, the map contains only values from earlier indices. If the complement is present, its stored index is different from the current index. Their values add to the target by definition of the complement. This gives a valid pair.

The loop uses enumerate to get each value and its index. Dictionary lookup and insertion are O(1) on average. We process the array at most once, so the expected time is O(n). In the worst case, the map stores up to n values, so the auxiliary space is O(n).

The key insight is to remember values that appeared earlier instead of checking every possible pair. For each current value, the algorithm asks whether the exact complement needed to reach the target is already in the map. The invariant is that the map stores only earlier values and their indices. Checking before insertion prevents reuse of the current element. This is more suitable than the direct nested loop, which may compare O(n²) pairs.

Let n be the number of elements. We process each element at most once and stop when the valid pair is found. Each Python dictionary lookup and insertion is O(1) on average, so the total expected time is O(n). The algorithm uses a dictionary to store earlier values and their indices. In the worst case, that dictionary can contain up to n entries, so the auxiliary space is O(n). This is the standard optimal expected-time approach for an unsorted array.

Common mistakes include returning [2, 7] instead of the required indices [0, 1], inserting the current value before checking the complement, and accidentally reusing the same element. Candidates may also sort the array and lose the original indices, forget that duplicate values such as [3, 3] must work, or claim guaranteed O(n) time instead of O(n) expected time for Python dictionary operations.

Before coding, say clearly: “My dictionary stores each earlier value and its index, and I check the complement before inserting the current value.”

I would use iterative binary search because the array is already sorted. I keep two inclusive boundaries, left and right, and repeatedly check the middle index. If nums[mid] equals the target, I return mid. If nums[mid] is smaller, I search the right half. Otherwise, I search the left half. When left becomes greater than right, the target is absent, so I return minus one. The time complexity is O(log n), and the auxiliary space is O(1).

The problem gives a sorted array and asks for the index of a target value. Because the values are sorted, we do not need to check every element one by one. The main idea is to compare the target with the middle value and remove half of the remaining search range each time.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is a sorted array of integers and a target value. The output is the target index if the target exists. If the target is absent, the function returns minus one. The answer is an index, not the value itself.

In the example, nums is [-1, 0, 3, 5, 9, 12] and target is 9. The value 9 appears at index 4, so the expected output is 4.

Binary search fits because the array is sorted. At each step, we check the middle value. If the middle value is too small, everything to its left is also too small. If the middle value is too large, everything to its right is also too large.

The invariant is that the target, if it still exists, must be inside the current left to right interval. Each update keeps that invariant true and makes the interval smaller.

We start with left = 0 and right = len(nums) - 1. These are inclusive boundaries, which means both ends are still part of the search range. The loop continues while left <= right because a one element range is still valid.

The midpoint is computed as left + (right - left) // 2. This gives the middle index of the current range. It also avoids overflow in languages with fixed size integers.

At step 1, left is 0 and right is 5. The middle index is 2, and nums[2] is 3. Since 3 is less than 9, the target must be to the right. We set left = mid + 1, so left becomes 3.

At step 2, left is 3 and right is 5. The middle index is 4, and nums[4] is 9. This equals the target, so we return 4 immediately. No later elements need to be processed.

The algorithm is correct because each comparison removes only the half that cannot contain the target. If nums[mid] is smaller than the target, all values at or before mid are too small. If nums[mid] is larger than the target, all values at or after mid are too large.

Important edge cases are an empty array, one element, target at the first index, target at the last index, and target absent. If duplicates are allowed, this implementation returns one matching index, not always the first.

The code stores the current interval in left and right. Inside the loop, it calculates mid and compares nums[mid] with target. A match returns mid. A smaller middle value moves left to mid + 1. A larger middle value moves right to mid - 1. If the loop ends, no valid index remains, so the code returns -1.

The key insight is that sorted order lets us discard half of the search space after each comparison. The algorithm keeps an inclusive interval from left to right. The central invariant is this: if the target still exists, it must be inside that interval. The midpoint divides the interval into two halves. When nums[mid] is smaller than the target, the left half cannot contain the answer. When nums[mid] is larger than the target, the right half cannot contain the answer. Each update reduces the interval until the target is found or the interval becomes empty.

The time complexity is O(log n), where n is the number of elements in the array. This happens because each loop removes about half of the remaining search range. For the example, the target is found after two checks. The auxiliary space complexity is O(1). The iterative solution uses only a few variables: left, right, and mid. It does not create another array, map, stack, or recursion call stack.

A common mistake is using left < right instead of left <= right for this inclusive version. That can skip the final one element interval. Another mistake is moving left to mid or right to mid. That may fail to reduce the interval and can cause an infinite loop. Some candidates return the target value instead of the index. Others forget to return -1 when the target is absent. Another mistake is applying binary search to an unsorted array.

Say clearly that the boundaries are inclusive. Then explain why each comparison safely removes one half. When coding, focus on the loop condition, midpoint calculation, and the two boundary updates. Those are the places where most binary search bugs happen.

I keep track of the lowest stock price seen so far and the best profit found so far. I process prices from left to right. If the current price is lower than the saved minimum, I update the minimum. Otherwise, I calculate the profit from selling today and keep the larger profit. This works because every selling day is compared with the cheapest earlier buying price. The solution runs in O(n) time and uses O(1) auxiliary space.

The input is a list of daily stock prices. We must buy on one day and sell on a later day. The goal is to return the largest possible profit. If no profitable transaction exists, we return 0. The solution uses a linear scan with two variables: min_price and max_profit.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is a list called prices. Each value is the stock price for one day.

The output is one integer. It is the largest profit from one buy followed by one later sell. We return 0 when every possible transaction would lose money or make no profit.

For the example prices = [7, 1, 5, 3, 6, 4], the answer is 5. We buy at index 1 for price 1. We sell later at index 4 for price 6. The profit is 6 - 1 = 5.

I scan the prices from left to right.

I keep min_price as the lowest price seen so far. I keep max_profit as the largest valid profit found so far.

The main invariant is simple. Whenever the current price is considered as a selling price, min_price is the lowest price found at an earlier index. This makes every calculated profit a valid buy-before-sell transaction.

I set min_price to positive infinity. Any real stock price will be smaller than this starting value.

I set max_profit to 0. This also handles cases where no profitable transaction exists.

At index 0, the price is 7. Since 7 is lower than infinity, min_price becomes 7. We do not calculate a profit on this step.

At index 1, the price is 1. Since 1 is lower than 7, min_price becomes 1. We do not calculate a profit on this step.

At index 2, the price is 5. It is not lower than min_price. The current profit is 5 - 1 = 4. max_profit becomes 4.

At index 3, the price is 3. The current profit is 3 - 1 = 2. This is smaller than 4, so max_profit stays 4.

At index 4, the price is 6. The current profit is 6 - 1 = 5. This is larger than 4, so max_profit becomes 5.

At index 5, the price is 4. The current profit is 4 - 1 = 3. This is smaller than 5, so max_profit stays 5.

After all prices are processed, the result is 5.

Whenever the current price is considered as a selling price, min_price is the lowest price from an earlier day. Subtracting min_price therefore gives the best profit possible for selling on that day.

The algorithm keeps the largest of these profits. Therefore, max_profit is the best profit across all valid buy-before-sell transactions.

The for loop processes each price from left to right.

The if branch updates min_price when a cheaper buying price is found. The else branch calculates the profit only when the current price is not a new minimum.

The max function keeps the larger value between the previous best profit and the current profit. After the loop, the function returns max_profit.

The time complexity is O(n) because each price is processed once. The auxiliary space complexity is O(1) because only a constant number of variables are stored.

If prices always decrease, max_profit stays 0. If all prices are equal, the answer is 0. An empty list or a one-element list also returns 0. Two prices produce either their positive difference or 0.

The key insight is that a selling price only needs to be compared with the lowest buying price seen before it. The algorithm keeps min_price as the lowest processed price and max_profit as the largest profit found. When a new lower price appears, it becomes the new possible buying price. Otherwise, the algorithm calculates price - min_price and updates max_profit. The invariant is that min_price is the cheapest valid earlier buying price whenever a sale is evaluated, while max_profit stores the best valid profit found so far.

The time complexity is O(n), where n is the number of prices. We make one pass through the list, and each price is processed one time. The auxiliary space complexity is O(1). Auxiliary space means extra memory used by the algorithm. The amount of extra memory does not grow with the input because we only keep a constant number of variables.

A common mistake is selling before buying. Process the list from left to right so the stored buying price always comes first. Another mistake is using two nested loops, which takes O(n²) time. Some candidates return the buy and sell prices even though this question asks for the profit. It is also incorrect to return a negative result when prices decrease. The required result is 0.

State the invariant before writing the loop: min_price is the lowest price seen so far, and max_profit is the best valid profit seen so far. This makes the code and correctness explanation much easier to follow.

I use a stack to store opening symbols that have not been matched yet. I process each character from left to right. When I see an opening symbol, I push it onto the stack. For a closing symbol, I check that the stack is not empty and that its top is the required opening type. Then I pop the match. The string is valid only when the stack is empty at the end. The time complexity is O(n), and the auxiliary space complexity is O(n).

The input is a string containing parentheses, square brackets, and braces. The function must return True only when every opening symbol is closed by the correct type in the correct order. A stack is a good fit because the most recent unmatched opening symbol must be closed first.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The function receives one string named s.

The possible opening symbols are (, [, and {.

The possible closing symbols are ), ], and }.

The function returns True when all opening symbols are matched by both type and order. It returns False when a closer has no matching opener, has the wrong opener, appears in the wrong order, or when an opener remains unmatched at the end.

The stack stores opening symbols that have not been matched yet. Each stack entry is one unmatched opening symbol. The top of the stack is the most recent opener.

The pairs dictionary maps each closing symbol to the opening symbol it requires:

) maps to ( ] maps to [ } maps to {

The main invariant is that after every processed character, the stack contains exactly the unmatched opening symbols from the processed part of the string. The most recent unmatched opener is always on top.

The stack starts empty:

stack = []

The closing-to-opening mapping is:

pairs = {')': '(', ']': '[', '}': '{'}

Traversal begins at index 0. The empty stack is correct because no characters have been processed yet.

The example input is "{[()]}".

Its length is 6.

The exact indices and characters are:

Index 0 contains { Index 1 contains [ Index 2 contains ( Index 3 contains ) Index 4 contains ] Index 5 contains }

Step 1 processes index 0. The current character is {. The stack before the step is []. The character is an opener, so it is pushed. The stack becomes ['{']. Processing continues.

Step 2 processes index 1. The current character is [. The stack before the step is ['{']. The character is an opener, so it is pushed. The stack becomes ['{', '[']. Processing continues.

Step 3 processes index 2. The current character is (. The stack before the step is ['{', '[']. The character is an opener, so it is pushed. The stack becomes ['{', '[', '(']. Processing continues.

Step 4 processes index 3. The current character is ). The stack before the step is ['{', '[', '(']. The pairs dictionary says that ) requires (. The stack is not empty, and its top is (. The types match, so the code pops (. The stack becomes ['{', '[']. Processing continues.

Step 5 processes index 4. The current character is ]. The stack before the step is ['{', '[']. The pairs dictionary says that ] requires [. The top is [, so the types match. The code pops [. The stack becomes ['{']. Processing continues.

Step 6 processes index 5. The current character is }. The stack before the step is ['{']. The pairs dictionary says that } requires {. The top is {, so the types match. The code pops {. The stack becomes [].

Traversal is complete after index 5. The final stack is empty, so the function returns True.

Every opening symbol is pushed onto the stack. A closing symbol is accepted only when it matches the most recent unmatched opening symbol at the top.

This checks the symbol type. It also checks the nesting order.

For example, "([)]" is invalid. When the code reaches ), the stack top is [. The required opener is (, so the function returns False.

The invariant remains true after every push and every valid pop. If the stack is empty at the end, every opening symbol has been matched. If the stack is not empty, at least one opener was never closed.

The function first creates the pairs dictionary and an empty stack.

It then reads each character from left to right.

If the character is in pairs, it is a closing symbol. The code first checks whether the stack is empty. It also checks whether the stack top is different from the required opener. If either condition is true, the function returns False immediately.

If the closer matches the top opener, the code pops that opener.

If the character is not in pairs, the code treats it as an opening symbol and pushes it onto the stack.

After the loop, return not stack returns True only when the stack is empty.

Let n be the number of characters in the string.

The time complexity is O(n). Each character is processed once. Every opening symbol is pushed once and popped at most once. The dictionary contains only three fixed mappings.

The auxiliary space complexity is O(n) in the worst case. The stack can contain many unmatched opening symbols.

The important edge cases shown in the diagram are:

An empty string returns True.

A string that starts with a closing symbol, such as "]", returns False.

A wrong type, such as "(]", returns False.

A wrong order, such as "([)]", returns False.

Unclosed opening symbols, such as "((", return False.

The key insight is that bracket matching follows last in, first out order. This means the most recent unmatched opening symbol must be closed before any earlier opening symbol. A stack provides this order directly. Opening symbols are pushed. For each closing symbol, the algorithm uses the pairs dictionary to find the required opener and compares it with the stack top. The invariant is that the stack always contains exactly the unmatched opening symbols from the processed prefix, with the most recent opener on top.

Let n be the length of the string. The time complexity is O(n) because each character is processed once. Every opening symbol is pushed once and popped at most once. Python dictionary membership and lookup are O(1) on average, and this dictionary has only three fixed entries. The auxiliary space complexity is O(n) because the stack may hold all opening symbols in the worst case. Auxiliary space means extra memory used by the algorithm.

A common mistake is popping before checking the opening-symbol type. The code must compare stack[-1] first and pop only after a match. Another mistake is trying to pop when the stack is empty. Some candidates check only whether the counts are equal, but equal counts do not prove correct order. Another mistake is forgetting to verify that the stack is empty after the loop. Candidates may also claim O(1) auxiliary space even though the stack can grow with the input.

Explain the invariant before writing the loop: the stack contains only unmatched opening symbols, and its top is the next opener that a closing symbol must match.

I would solve this iteratively with two pointers and a dummy node. One pointer starts at the head of each sorted list. I compare the two current node values and attach the node with the smaller value. When the values are equal, I attach the node from List 1. I then move that list’s pointer forward. When one list ends, I attach the remaining chain. The time complexity is O(n + m), and the auxiliary space complexity is O(1).

This problem asks us to merge two already sorted linked lists into one sorted linked list. The best fit here is an iterative two-pointer method. We reuse the existing nodes, compare only the current heads, and build the result from left to right. A dummy node gives us a fixed starting point and avoids special handling for the first merged node.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is the head of List 1 and the head of List 2. Both lists are sorted in non-decreasing order. We must return the head of one merged sorted linked list.

For the example:

List 1: 1 → 2 → 4

List 2: 1 → 3 → 4

The returned list is:

1 → 1 → 2 → 3 → 4 → 4

We return node references, not a new array of values.

We use pointer p1 for List 1 and pointer p2 for List 2. At each step, we compare p1.val and p2.val. We attach the node with the smaller value. When the values are equal, the code attaches the node from List 1 because it uses the condition p1.val <= p2.val.

We also use a dummy node and a tail pointer. dummy is a fixed starting node. tail always points to the last node in the merged part built so far.

The central invariant is this: the nodes after dummy are always sorted, contain exactly the nodes already selected from both lists, and tail points to the last selected node.

Create a dummy node. Set tail to dummy.

Set p1 to the head of List 1 and p2 to the head of List 2.

At the start:

p1 points to value 1 in List 1.

p2 points to value 1 in List 2.

The merged list after dummy is empty.

Step 1: p1 is 1 and p2 is 1. Since 1 <= 1, attach the node from List 1. Move p1 to 2. Move tail to the attached node. The merged values are now 1.

Step 2: p1 is 2 and p2 is

1. Since 2 > 1, attach the node from List
2. Move p2 to
3. Move tail forward. The merged values are now 1 → 1.

Step 3: p1 is 2 and p2 is 3. Since 2 <= 3, attach 2 from List 1. Move p1 to 4. The merged values are now 1 → 1 → 2.

Step 4: p1 is 4 and p2 is 3. Since 4 > 3, attach 3 from List 2. Move p2 to 4. The merged values are now 1 → 1 → 2 → 3.

Step 5: p1 is 4 and p2 is 4. Since 4 <= 4, attach the node from List 1. Move p1 to None. The merged values are now 1 → 1 → 2 → 3 → 4.

Step 6: List 1 is exhausted. Attach the remaining List 2 chain starting at node 4. We do not move p2 or tail because the whole remaining chain is linked in one operation. The final merged list is 1 → 1 → 2 → 3 → 4 → 4.

At every step, p1 and p2 point to the smallest remaining nodes in their own lists. Choosing the node with the smaller value is safe because no later node in either sorted list can be smaller. When the values are equal, choosing the List 1 node first still keeps the merged list sorted.

This keeps the merged prefix sorted. We never skip a node. When one list ends, every remaining node in the other list is already sorted and is greater than or equal to the last selected node. Therefore, attaching the remaining chain keeps the final list sorted.

The loop runs while both pointers are not None. It compares p1.val and p2.val. If p1.val <= p2.val, it attaches p1 and advances p1. Otherwise, it attaches p2 and advances p2. After either choice, tail moves to the node that was just attached.

After the loop, at least one pointer is None. The line tail.next = p1 if p1 is not None else p2 attaches the entire remaining chain in one operation.

Finally, dummy.next is returned because it points to the real head of the merged list.

Let n be the number of nodes in List 1 and m be the number of nodes in List 2. Each node chosen during comparison is processed once, and any remaining chain is attached directly. In the worst case, the algorithm examines all nodes, so the time complexity is O(n + m).

The algorithm uses only dummy, tail, p1, and p2. It does not create a new node for every value. Therefore, the auxiliary space complexity is O(1).

Relevant edge cases are one empty list, both lists empty, duplicate values, and one list containing only values smaller than the other list.

The key idea is to use the fact that both linked lists are already sorted. We only need to compare the two current head nodes. We attach the node with the smaller value. When the values are equal, the code chooses the node from List 1 because it uses p1.val <= p2.val. We then advance only the pointer from the selected list. A dummy node gives us a stable starting point, while tail marks the end of the merged prefix. The invariant is that dummy.next through tail is always sorted and contains exactly the nodes already selected from the two lists. Once one list is exhausted, the remaining chain from the other list can be attached directly because it is already sorted.

Let n be the number of nodes in the first list and m be the number of nodes in the second list. Each node selected during comparison is processed once, and any remaining chain is attached directly. In the worst case, the algorithm examines all nodes, so the time complexity is O(n + m). It uses only a fixed number of extra pointers: dummy, tail, p1, and p2. It reuses the existing list nodes instead of copying them into another structure. Therefore, the auxiliary space complexity is O(1). The dummy node is only one extra node, so the extra memory does not grow with the input size.

A common mistake is moving the wrong pointer after attaching a node. The pointer from the selected list must move forward. Another mistake is forgetting the exact equal-value rule. With the condition p1.val <= p2.val, the node from List 1 is selected when both values are equal. Candidates may also forget to move tail after each attachment or forget to attach the remaining chain after the main loop. Returning dummy instead of dummy.next adds the placeholder node to the result. It is also incorrect to claim that this iterative solution uses O(n + m) auxiliary space because it reuses the existing nodes and uses O(1) extra space.

State the invariant before coding: the list after dummy is always sorted, and tail points to the last node in that merged prefix. Also mention that <= chooses List 1 when the current values are equal.

I would use a monotonic stack that stores indices of days that are still waiting for a warmer temperature. I scan the temperatures from left to right. While the current temperature is warmer than the temperature at the index on top of the stack, I pop that index and calculate the day difference. Then I push the current index. Each index is pushed and popped at most once, so the time complexity is O(n). The auxiliary space complexity is O(n).

The problem asks us to return, for each day, how many days we must wait for a warmer temperature. If no warmer day exists, the answer for that position stays zero. A monotonic stack fits this problem because it keeps the indices of unresolved days and lets a warmer day resolve several earlier days efficiently.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is a list of temperatures.

For the example:

Input: [73, 74, 75, 71, 69, 72, 76, 73]

The output must contain one number for each input position:

Output: [1, 1, 4, 2, 1, 1, 0, 0]

Each output value tells us how many days we must wait for a strictly warmer temperature. Equal temperatures do not count as warmer.

The stack stores indices, not temperatures.

Each stored index represents a day that has not found a warmer future day yet.

The temperatures at those indices are non-increasing from the bottom of the stack to the top. This means the top is the most recent unresolved day and is the first one we compare with the current temperature.

Create a result list filled with eight zeros:

[0, 0, 0, 0, 0, 0, 0, 0]

Create an empty stack:

[]

A zero remains in the result when no warmer future day is found.

At index 0, the temperature is 73. The stack is empty, so push index 0.

Stack: [0]

At index 1, the temperature is 74. It is warmer than 73 at index 0. Pop index 0 and set result[0] = 1 - 0 = 1. Then push index 1.

Stack: [1]

Result: [1, 0, 0, 0, 0, 0, 0, 0]

At index 2, the temperature is 75. It is warmer than 74 at index 1. Pop index 1 and set result[1] = 2 - 1 = 1. Then push index 2.

Stack: [2]

Result: [1, 1, 0, 0, 0, 0, 0, 0]

At index 3, the temperature is 71. It is not warmer than 75 at index 2, so push index 3.

Stack: [2, 3]

At index 4, the temperature is 69. It is not warmer than 71 at index 3, so push index 4.

Stack: [2, 3, 4]

At index 5, the temperature is 72. It is warmer than 69 at index 4. Pop index 4 and set result[4] = 5 - 4 = 1.

It is also warmer than 71 at index 3. Pop index 3 and set result[3] = 5 - 3 = 2.

It is not warmer than 75 at index 2, so stop popping and push index 5.

Stack: [2, 5]

Result: [1, 1, 0, 2, 1, 0, 0, 0]

At index 6, the temperature is 76. It is warmer than 72 at index 5. Pop index 5 and set result[5] = 6 - 5 = 1.

It is also warmer than 75 at index 2. Pop index 2 and set result[2] = 6 - 2 = 4.

Then push index 6.

Stack: [6]

Result: [1, 1, 4, 2, 1, 1, 0, 0]

At index 7, the temperature is 73. It is not warmer than 76 at index 6, so push index 7.

Final stack: [6, 7]

The remaining indices have no warmer future day, so their result values remain zero.

The stack contains only unresolved days.

When the current temperature is warmer than the temperature at the top index, the current day is the first warmer day for that stored index. No earlier day could have resolved it, because that index would already have been removed from the stack.

The distance is current_index - previous_index. After an index is popped, its answer is complete and never changes.

The code loops through each temperature with its index. The while loop resolves every previous day that is cooler than the current day. For each popped index, the code stores the distance to the current index. The current index is then pushed onto the stack. After the loop, unresolved indices keep their initial value of zero.

Each index is pushed onto the stack once and popped at most once. Therefore, the total time complexity is O(n).

The monotonic stack can hold up to n indices, so the auxiliary space complexity is O(n). The returned result list also uses O(n) output space.

Important edge cases include an empty list, one temperature, strictly decreasing temperatures, strictly increasing temperatures, and equal temperatures.

The key insight is to delay the answer for a day until a warmer temperature appears. The stack stores indices of unresolved days. Their temperatures are non-increasing from bottom to top. When a warmer temperature arrives, it can resolve one or more indices from the top of the stack. The first warmer day found for a popped index is the correct answer because all earlier processed temperatures failed to resolve it. This avoids checking every future day for every position.

Let n be the number of temperatures. The time complexity is O(n). Although there is a while loop inside the for loop, each index enters the stack once and leaves the stack at most once. The auxiliary space complexity is O(n) because the stack may store up to n indices. The returned result list also uses O(n) output space.

A common mistake is storing temperatures instead of indices. The index is needed to calculate the number of days. Another mistake is popping when temperatures are equal. The question requires a strictly warmer day, so the comparison must use less than, not less than or equal to. Candidates may also pop only one item instead of continuing while several earlier days are cooler. Another mistake is claiming O(n²) time because of the nested loops. Each index is popped at most once, so the total time is O(n). Finally, do not overwrite the remaining zeros because they correctly represent days with no warmer future temperature.

State the stack invariant before coding: the stack stores unresolved indices whose temperatures are non-increasing from bottom to top. Then explain that each warmer day repeatedly resolves cooler indices from the top.