Myntra interview questions & answers

17 real Myntra interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (17 Myntra questions in total).

CodingEasyMyntraSoftware Engineer

1. Remove Duplicates from Sorted Array (LeetCode)

Model answer

The task

Given a sorted list of integers, modify it in place so each distinct value appears once in the front. Return the length of that unique prefix.

Key idea

Because the values are sorted, duplicates are adjacent. Keep a read pointer to scan the list and a write pointer for the next position where a new value belongs.

Approach

  1. If the list is empty, return 0.
  2. Start the write pointer at 1, since the first value is already unique.
  3. Scan from left to right.
  4. When the current value differs from the last value written, copy it to the write position and advance the pointer.
  5. Return the write pointer as the unique-prefix length.
from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        write = 1

        # Copy each newly encountered value into the unique prefix.
        for read in range(1, len(nums)):
            if nums[read] != nums[write - 1]:
                nums[write] = nums[read]
                write += 1

        return write

Complexity:

  • Time: O(n), where n is the length of the list.
  • Space: O(1), since the list is modified in place using only a fixed number of variables.

Common follow-ups

  • What if the list is not sorted? Use a set to track seen values while compacting unique values in their original order.
  • What if each value may appear at most twice? Write a value when fewer than two values have been written, or when it differs from the value two positions back.
  • What if the list is very large and cannot fit in memory? Process sorted chunks while carrying the last value across chunk boundaries.
CodingEasyMyntraSoftware Engineer

2. Find Pivot Index (LeetCode)

Model answer

The task

Given an integer array, return the leftmost index where the sum of the elements before it equals the sum of the elements after it. Return -1 if no such index exists.

Key idea

Compute the total sum once, then scan from left to right while maintaining the sum to the left. At each index, the right sum is the total minus the left sum and the current element.

Approach

  1. Sum all elements to get the total.
  2. Initialize the running left sum to zero.
  3. For each index, compare the left sum with total - left_sum - nums[index].
  4. Return the index when the sums match; otherwise, add the current value to the left sum.
  5. Return -1 if the scan finishes without a match.
from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        left_sum = 0

        for i, value in enumerate(nums):
            right_sum = total - left_sum - value

            if left_sum == right_sum:
                return i

            left_sum += value

        return -1

Complexity:

  • Time: O(n), for one pass through the array after summing it.
  • Space: O(1), using only a fixed number of extra variables.

Common follow-ups

  • What if there are multiple pivot indices? The left-to-right scan returns the first; collect each matching index instead if all are required.
  • Can this handle negative values? Yes. The equality check relies on sums, not on values being positive.
  • What if the array is updated repeatedly? A single update changes the sums for many indices; a Fenwick tree or segment tree can support range-sum queries and updates more efficiently.
CodingEasyMyntraSoftware Engineer

3. Best Time to Buy and Sell Stock (LeetCode)

Model answer

The task

Given daily stock prices, find the greatest profit possible from one buy followed by one later sale. If no sale would make money, return zero.

Key idea

As we scan the prices, keep the lowest price seen so far. Treat each current price as a possible sale and update the best profit using the difference from that minimum.

Approach

  1. Initialize the minimum price to a value larger than any price and the best profit to zero.
  2. Visit each price in order.
  3. Update the minimum price with the current price.
  4. Check the profit from selling today and update the best profit.
  5. Return the best profit.
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float("inf")
        best_profit = 0

        for price in prices:
            # The current price can be a new best day to buy.
            min_price = min(min_price, price)

            # Or it can be the day to sell after the cheapest earlier buy.
            best_profit = max(best_profit, price - min_price)

        return best_profit

Complexity:

  • Time: O(n), where n is the number of prices; each is processed once.
  • Space: O(1), since only a few variables are stored.

Common follow-ups

  • What if multiple buy-and-sell transactions are allowed? Sum the gains from every adjacent price increase.
  • What if a transaction fee is charged? Track the best holding and non-holding profits, incorporating the fee when selling.
  • What if at most k transactions are allowed? Use dynamic programming over the number of completed transactions and whether a share is currently held.
CodingMediumMyntraSoftware Engineer

4. Rotting Oranges (LeetCode)

Model answer

The task

Given a grid of empty cells, fresh oranges, and rotten oranges, find the minimum number of minutes until no fresh oranges remain. Each minute, a rotten orange makes any fresh orange directly above, below, left, or right of it rotten; return -1 if some fresh oranges can never be reached.

Key idea

Use multi-source breadth-first search: all initially rotten oranges spread at the same time, so put them all in the queue at the start. Process the queue one minute at a time, counting newly rotten oranges to detect whether any fresh ones remain unreachable.

Approach

  1. Count the fresh oranges and enqueue every initially rotten orange.
  2. If there are no fresh oranges, return 0.
  3. For each BFS layer, rot adjacent fresh oranges, decrement the fresh count, and enqueue them.
  4. Count each processed layer as one minute.
  5. Return the minutes if all fresh oranges rotted; otherwise return -1.
from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh = 0

        # Gather all initial sources and count oranges that still need to rot.
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    queue.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1

        if fresh == 0:
            return 0

        minutes = 0
        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

        while queue and fresh > 0:
            # Process exactly the oranges rotten before this minute began.
            for _ in range(len(queue)):
                r, c = queue.popleft()

                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if (
                        0 <= nr < rows
                        and 0 <= nc < cols
                        and grid[nr][nc] == 1
                    ):
                        grid[nr][nc] = 2
                        fresh -= 1
                        queue.append((nr, nc))

            minutes += 1

        return minutes if fresh == 0 else -1

Complexity:

  • Time: O(rows × cols), since each cell is visited at most once.
  • Space: O(rows × cols) for the BFS queue in the worst case.

Common follow-ups

  • What if diagonal neighbors also spread rot? Add the four diagonal directions to the neighbor list.
  • Can the original grid be preserved? Copy it first, or track visited cells separately.
  • How would you return which oranges rot each minute? Store each BFS layer’s cells or record a rot-time value per cell.
CodingMediumMyntraSoftware Engineer

5. 3Sum (LeetCode)

Model answer

The task

Given an integer array, return every distinct triplet of values whose sum is zero. Triplets are considered the same if they contain the same values, regardless of order.

Key idea

Sort the array, then fix each value in turn and use two pointers to find pairs that complete its sum to zero. Skipping repeated values prevents duplicate triplets.

Approach

  1. Sort the input array.
  2. For each index, treat its value as the first element of a triplet.
  3. Skip the index if its value is the same as the previous value.
  4. Set two pointers immediately after the fixed index and at the end of the array.
  5. Move a pointer according to whether the current sum is too small or too large.
  6. When a triplet is found, record it and advance past duplicate pointer values.
from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        triplets = []
        n = len(nums)

        for i in range(n - 2):
            # Only use the first occurrence of each fixed value.
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    triplets.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # Avoid repeating the same pair for this fixed value.
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

        return triplets

Complexity:

  • Time: O(n²), from fixing each value and scanning with two pointers.
  • Space: O(n) for Python's in-place sort; excludes the returned triplets.

Common follow-ups

  • How would you return unique index triplets instead of value triplets? Track original indices while sorting, then return the corresponding index triples.
  • What if the target sum is a variable? Replace the zero-sum check with a comparison against the target.
  • Can the approach be extended to four values? Fix two values and use two pointers for the remaining pair, giving O(n³) time.
CodingMediumMyntraSoftware Engineer

6. Maximum Earnings From Taxi (LeetCode)

Model answer

The task

Given a destination distance and a list of rides, choose compatible rides to maximize total earnings. A ride earns its distance plus its tip, and another ride may begin as soon as the previous one ends.

Key idea

Sort rides by ending point and use dynamic programming. For each ride, binary-search how many earlier rides finish no later than its start; then compare taking it with skipping it.

Approach

  1. Sort rides by end point.
  2. Store the sorted end points for binary searches.
  3. For each ride, find the count of earlier rides that do not overlap it.
  4. Set the best earnings so far to the maximum of skipping the ride or adding its earnings to the compatible prefix’s best total.
  5. Return the best total.
from bisect import bisect_right
from typing import List

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides.sort(key=lambda ride: ride[1])
        ends = [end for _, end, _ in rides]

        # dp[i] is the best earnings using the first i rides.
        dp = [0] * (len(rides) + 1)

        for i, (start, end, tip) in enumerate(rides):
            # Count earlier rides that finish by this ride's start.
            compatible_count = bisect_right(ends, start, 0, i)
            earnings = end - start + tip

            dp[i + 1] = max(
                dp[i],  # Skip this ride.
                dp[compatible_count] + earnings,  # Take this ride.
            )

        return dp[-1]

Complexity:

  • Time: O(m log m), for sorting and one binary search per ride.
  • Space: O(m), for the sorted end points and DP array, where m is the number of rides.

Common follow-ups

  • How would you handle rides that can overlap at endpoints? Adjust the binary-search comparison to match whether endpoint sharing is allowed.
  • Can the DP be computed by start point instead? Yes; sort by start and use a reverse DP with a search for the next compatible ride.
  • What if rides arrive online? The sorted offline DP relies on knowing ride order; online variants need an ordered structure and may require additional assumptions about incoming rides.
CodingMediumMyntraSoftware Engineer

7. Capacity To Ship Packages Within D Days (LeetCode)

Model answer

The task

Find the smallest ship capacity that can transport all packages within the given number of days, shipping packages in their original order.

Key idea

If a capacity works, any larger capacity also works, so feasibility is monotonic and can be searched with binary search. For a candidate capacity, greedily load each day as many consecutive packages as fit.

Approach

  1. The capacity must be at least the heaviest package.
  2. The sum of all weights is always sufficient, since it can ship everything in one day.
  3. Binary-search this range.
  4. For each candidate, greedily count how many days are needed, starting a new day when the next package would exceed capacity.
  5. Keep the candidate if the required days are within the limit; otherwise, increase the capacity.
class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def can_ship(capacity: int) -> bool:
            used_days = 1
            load = 0

            for weight in weights:
                if load + weight > capacity:
                    used_days += 1
                    load = 0

                load += weight

            return used_days <= days

        left = max(weights)
        right = sum(weights)

        while left < right:
            capacity = (left + right) // 2

            if can_ship(capacity):
                right = capacity
            else:
                left = capacity + 1

        return left

Complexity:

  • Time: O(n log(sum(weights) - max(weights) + 1)), for the binary search and feasibility checks.
  • Space: O(1), excluding the input.

Common follow-ups

  • What if packages can be reordered? The greedy check changes; for positive weights, packing the largest packages first may help, but the original-order constraint is essential to this solution.
  • Can you return the day-by-day assignments too? Record each greedy day’s packages during a final feasibility pass.
  • What if the number of days is very large? The same bounds and binary search apply; capacities below the heaviest package remain impossible.
CodingMediumMyntraSoftware Engineer

8. Deepest Leaves Sum (LeetCode)

Model answer

The task

Given the root of a binary tree, return the sum of the values of all leaves that are at the greatest depth.

Key idea

A breadth-first search visits the tree one level at a time. Keep the sum for the current level; when the traversal ends, that sum belongs to the deepest level.

Approach

  1. Return 0 if the tree is empty.
  2. Put the root in a queue.
  3. For each level, process exactly the nodes currently in the queue.
  4. Add their values to a level sum and enqueue their children.
  5. Return the sum from the final level processed.
from collections import deque
from typing import Optional

# Assumes the usual binary-tree node definition:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def deepestLeavesSum(self, root: Optional["TreeNode"]) -> int:
        if root is None:
            return 0

        queue = deque([root])
        deepest_level_sum = 0

        while queue:
            level_sum = 0

            # Process only the nodes present at the start of this level.
            for _ in range(len(queue)):
                node = queue.popleft()
                level_sum += node.val

                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)

            # Each iteration moves one level deeper, so the last sum is
            # the sum of the deepest level.
            deepest_level_sum = level_sum

        return deepest_level_sum

Complexity:

  • Time: O(n), since every node is visited once.
  • Space: O(w), where w is the maximum number of nodes at any one level in the queue.

Common follow-ups

  • How would you solve it with depth-first search? Track the greatest depth seen and replace or accumulate the sum when visiting leaves.
  • What if the tree is very deep? An iterative traversal avoids recursion-stack limits.
  • What if the tree is empty? Return 0, as handled above.
CodingMediumMyntraSoftware Engineer

9. Generate Parentheses (LeetCode)

Model answer

The task

Given a nonnegative number of pairs, return every string of that many opening and closing parentheses that is correctly balanced.

Key idea

Build each string one character at a time. Add an opening parenthesis only while fewer than n have been used, and add a closing parenthesis only when it will not outnumber the openings already used.

Approach

  1. Track how many opening and closing parentheses have been added, plus the current string.
  2. If the string has length 2 * n, save it.
  3. Recurse with an opening parenthesis when fewer than n openings have been used.
  4. Recurse with a closing parenthesis when fewer closings have been used than openings.
  5. Start with an empty string and zero counts.
from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        results: List[str] = []
        current: list[str] = []

        def backtrack(open_count: int, close_count: int) -> None:
            if len(current) == 2 * n:
                results.append("".join(current))
                return

            if open_count < n:
                current.append("(")
                backtrack(open_count + 1, close_count)
                current.pop()

            if close_count < open_count:
                current.append(")")
                backtrack(open_count, close_count + 1)
                current.pop()

        backtrack(0, 0)
        return results

Complexity:

  • Time: O(Cₙ · n), where Cₙ is the number of valid strings; each is assembled in O(n) time.
  • Space: O(n) auxiliary space for the recursion and current string, excluding the returned results.

Common follow-ups

  • How can you count the results without generating them? Use the Catalan number formula, Cₙ = binomial(2n, n) / (n + 1).
  • What happens when n is zero? The algorithm returns a list containing the empty string.
  • How would you generate strings with multiple bracket types? Track each type’s balance and ensure closing brackets match the most recent unmatched opening bracket.
CodingMediumMyntraSoftware Engineer

10. Container With Most Water (LeetCode)

Model answer

The task

Given nonnegative heights arranged along a line, choose two positions to form a container with the greatest possible area. Its area is the distance between the positions multiplied by the shorter of their two heights.

Key idea

Start with the widest possible pair, at the two ends. The shorter side limits the area, so moving the taller side inward cannot improve that limiting height and only reduces the width. Move the shorter side instead, hoping to find a taller boundary.

Approach

  1. Set pointers to the first and last positions.
  2. Compute the area using their distance and the shorter height; update the best area.
  3. Move the pointer at the shorter height inward by one position.
  4. Repeat until the pointers meet.
  5. Return the greatest area seen.
from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        best_area = 0

        while left < right:
            width = right - left
            limiting_height = min(height[left], height[right])
            best_area = max(best_area, width * limiting_height)

            # The shorter side limits this container's area.
            # Moving the taller side inward cannot improve that limit.
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

        return best_area

Complexity:

  • Time: O(n), because each pointer moves inward at most n times.
  • Space: O(1), since only a few variables are used.

Common follow-ups

  • What if heights can be negative? A negative height does not describe a valid container; clarify the input rules, or treat invalid heights as unusable.
  • Why is it safe to discard the shorter side? With the same shorter boundary, every inward pair has less width, so it cannot produce a larger area.
  • Can this be done with extra memory? Not usefully for this objective; the two-pointer scan already processes the candidates in linear time with constant space.
CodingMediumMyntraSoftware Engineer

11. Target Sum (LeetCode)

Model answer

The task

Count the ways to assign a plus or minus sign to each number so their signed sum equals the target.

Key idea

Let P be the sum of numbers assigned a plus sign, and let S be the sum of all numbers. Then the minus-assigned numbers sum to S - P, so P = (S + target) / 2. The problem becomes counting subsets with that sum.

Approach

  1. Compute the total sum S.
  2. Return 0 if the target is out of range or S + target is odd.
  3. Set the subset-sum capacity to (S + target) // 2.
  4. Use 1D dynamic programming, where dp[s] counts subsets summing to s.
  5. Process each number in descending sum order so it is used at most once.
from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)

        # A signed sum cannot exceed the total magnitude.
        if abs(target) > total:
            return 0

        combined = total + target
        if combined % 2 != 0:
            return 0

        capacity = combined // 2
        dp = [0] * (capacity + 1)
        dp[0] = 1

        for value in nums:
            # Descending order prevents reusing this value.
            # When value is zero, each count is correctly doubled.
            for current_sum in range(capacity, value - 1, -1):
                dp[current_sum] += dp[current_sum - value]

        return dp[capacity]

Complexity:

  • Time: O(nP), where n is the number of values and P = (S + target) / 2.
  • Space: O(P) for the subset-sum counts.

Common follow-ups

  • How would you return the actual sign assignments? Store predecessors or use backtracking with memoization.
  • What if the input can contain negative values? Use a map of reachable sums to counts instead of the subset-sum transformation.
  • How can you reduce the DP memory further? The 1D array is already the standard space-optimized form for this approach.
CodingMediumMyntraSoftware Engineer

12. Wiggle Sort (LeetCode)

Model answer

The task

Rearrange the array in place so its values alternate between low and high: each even-indexed value is no greater than its next value, and each odd-indexed value is no less than its next value.

Key idea

Check each adjacent pair once. At every position, enforce the inequality required by the alternating pattern by swapping the pair only when it is out of order. Earlier pairs remain valid because a swap changes only the current pair.

Approach

  1. Scan the array from left to right, comparing each element with its successor.
  2. At an even index, swap if the left value is greater than the right.
  3. At an odd index, swap if the left value is less than the right.
  4. Return after the single pass; the array is modified in place.
from typing import List

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """Rearrange nums in place into a low-high wiggle pattern."""
        for i in range(len(nums) - 1):
            if i % 2 == 0:
                # Even-indexed values should be no greater than the next.
                if nums[i] > nums[i + 1]:
                    nums[i], nums[i + 1] = nums[i + 1], nums[i]
            else:
                # Odd-indexed values should be no less than the next.
                if nums[i] < nums[i + 1]:
                    nums[i], nums[i + 1] = nums[i + 1], nums[i]

Complexity:

  • Time: O(n), because the array is scanned once.
  • Space: O(1), because swaps use only constant extra space.

Common follow-ups

  • What if the pattern must start high-low? Reverse the inequalities checked at even and odd indices.
  • What if every inequality must be strict? This greedy method does not guarantee that; duplicates can make a strict arrangement impossible.
  • Why do later swaps preserve earlier pairs? At each step, only the pair beginning at the current index changes, so already-checked pairs are untouched.
CodingMediumMyntraSoftware Engineer

13. Longest Consecutive Sequence (LeetCode)

Model answer

The task

Given an integer array, return the length of its longest run of consecutive values, regardless of their order in the array.

Key idea

Put the values in a set for fast membership checks. Only start counting from a value whose predecessor is absent, so each consecutive run is scanned once.

Approach

  1. Convert the array to a set, removing duplicates.
  2. For each distinct value, check whether its predecessor is in the set.
  3. If not, count upward while consecutive values remain present.
  4. Track and return the longest count.
from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        values = set(nums)
        longest = 0

        for value in values:
            # Only begin counting at the start of a consecutive run.
            if value - 1 not in values:
                current = value
                length = 1

                while current + 1 in values:
                    current += 1
                    length += 1

                longest = max(longest, length)

        return longest

Complexity:

  • Time: O(n) on average; each distinct value is checked a constant number of times.
  • Space: O(n) for the set of distinct values.

Common follow-ups

  • How should an empty array be handled? The implementation returns 0.
  • What if the input contains duplicates? The set removes them without affecting the run length.
  • Can this be solved with sorting? Yes; sort the values and scan adjacent differences, taking O(n log n) time.
  • How could Union-Find be used? Treat each value as a node, union neighboring values that exist, then find the largest component.
CodingMediumMyntraSoftware Engineer

14. Longest Substring Without Repeating Characters (LeetCode)

Model answer

The task

Find the length of the longest contiguous section of a string in which every character appears at most once.

Key idea

Maintain a sliding window with no repeated characters. When a character repeats within the window, move the left edge just past its previous occurrence.

Approach

  1. Track each character’s most recent index in a dictionary.
  2. Keep left as the window’s starting index and best as its longest length so far.
  3. For each character, move left forward if its previous occurrence is inside the current window.
  4. Record the character’s current index and update best using the window length.
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        left = 0
        best = 0

        for right, char in enumerate(s):
            # Skip past a repeated character if it is in the current window.
            if char in last_seen and last_seen[char] >= left:
                left = last_seen[char] + 1

            last_seen[char] = right
            best = max(best, right - left + 1)

        return best

Complexity:

  • Time: O(n), because each character is processed once.
  • Space: O(k), where k is the number of distinct characters encountered.

Common follow-ups

  • Return the substring itself: store the best window’s start and end indices when updating best.
  • Handle a stream of characters: keep the same window state and process each arriving character incrementally.
  • Use a fixed-size character set: replace the dictionary with an array of last-seen indices.
CodingMediumMyntraSoftware Engineer

15. Minimum Moves to Equal Array Elements II (LeetCode)

Model answer

The task

Find the fewest total single-unit increases or decreases needed to make every array element equal.

Key idea

For a sum of absolute differences, a median minimizes the total cost. So we can sort the values, choose a middle value, and sum each value’s distance from it.

Approach

  1. Sort the array.
  2. Select the middle element as the target.
  3. Sum the absolute difference between each element and the target.
  4. Return that sum.
from typing import List

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        # A median minimizes the sum of absolute differences.
        nums.sort()
        target = nums[len(nums) // 2]

        # Count the moves needed to bring every value to the target.
        return sum(abs(value - target) for value in nums)

Complexity:

  • Time: O(n log n), due to sorting.
  • Space: O(n), for the temporary storage used by Python’s sort.

Common follow-ups

  • Can you avoid fully sorting? Use quickselect to find a median in O(n) average time.
  • What if the array is already sorted? The same median choice and distance sum apply.
  • What if the target must be a specified value? Sum each element’s absolute difference from that value instead.
CodingHardMyntraSoftware Engineer

16. Largest Rectangle in Histogram (LeetCode)

Model answer

The task

Given bar heights in a histogram, find the largest area of a rectangle that fits entirely beneath consecutive bars.

Key idea

For each bar, treat its height as the rectangle’s limiting height. A monotonic stack lets us find the widest span for each such height when we encounter a shorter bar.

Approach

  1. Scan the bars from left to right, keeping indices in a stack whose heights are non-decreasing.
  2. When the current bar is shorter than the stack’s top, pop that bar: the current index is its first shorter bar on the right.
  3. The new stack top, if present, marks the first shorter bar on the left. Compute the area across the span between those boundaries.
  4. Process a virtual height of zero after the last bar to resolve all remaining indices.
  5. Track and return the largest area found.
class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        best = 0
        stack = []
        n = len(heights)

        # The virtual zero-height bar closes every remaining span.
        for i in range(n + 1):
            current_height = heights[i] if i < n else 0

            while stack and heights[stack[-1]] > current_height:
                height = heights[stack.pop()]

                # The new top is the nearest shorter bar to the left.
                left_boundary = stack[-1] if stack else -1
                width = i - left_boundary - 1
                best = max(best, height * width)

            # Do not store the virtual bar's index.
            if i < n:
                stack.append(i)

        return best

Complexity:

  • Time: O(n), since each bar is pushed and popped at most once.
  • Space: O(n), for the stack in the worst case.

Common follow-ups

  • How would you handle bars with different widths? Use cumulative horizontal positions to calculate span widths.
  • How can this solve the maximal rectangle in a binary matrix? Build histogram heights row by row and apply this method to each row.
  • What if bar heights change and queries arrive between updates? A segment tree can store range summaries, though supporting arbitrary updates efficiently is more involved.
CodingHardMyntraSoftware Engineer

17. First Missing Positive (LeetCode)

Model answer

The task

Given an integer array, return the smallest positive integer that does not appear in it. The answer must be found in linear time using constant extra space.

Key idea

For an array of length n, the answer must be between 1 and n + 1. Place each value x in the slot at index x - 1 whenever x is in the range 1..n. Then the first slot that does not contain its expected value reveals the answer.

Approach

  1. Let n be the array length.
  2. Scan the array and place each in-range value into its corresponding slot.
  3. Skip values already in the correct slot to avoid looping on duplicates.
  4. Scan again; return the first index whose value is not index + 1.
  5. If every slot matches, return n + 1.
from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0

        # Put each value x in the slot at index x - 1, when possible.
        while i < n:
            value = nums[i]
            target = value - 1

            if 1 <= value <= n and nums[target] != value:
                nums[i], nums[target] = nums[target], nums[i]
            else:
                i += 1

        # The first misplaced value indicates the missing positive.
        for i, value in enumerate(nums):
            if value != i + 1:
                return i + 1

        return n + 1

Complexity:

  • Time: O(n), since each successful swap places a value in its final slot.
  • Space: O(1), using the input array for rearrangement.

Common follow-ups

  • What if the input must remain unchanged? Copy it first, using O(n) extra space.
  • Why can values larger than n be ignored? The smallest missing positive is at most n + 1.
  • What happens with duplicates? The swap condition skips a value already in its target slot.
  • Can the array be rearranged arbitrarily? Yes; the required result depends only on which positive values are present.

Practice these out loud, don't memorise them

Reading an answer is not the same as being able to give one under pressure. ChannelPulse plays the interviewer, asks the follow-ups, and scores each answer with feedback and a model answer so you can hear the gap between what you said and what lands.

Get ChannelPulse Browse all questions