PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

Solve increasing sequence and path problems evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

  • Medium
  • Meta
  • Coding & Algorithms
  • Software Engineer

Solve increasing sequence and path problems

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Answer the following related tasks about increasing sequences and paths: a) Contiguous subarray: Given an integer array nums, find the longest strictly increasing contiguous subarray. Return the length and the start/end indices of any one such subarray. Example: nums = [1, 2, 1, 2, 3] -> length = 3 with subarray [1, 2, 3]. Target time O(n), space O( 1). State how you break ties when multiple subarrays have the same maximum length. b) Subsequence (not necessarily contiguous): Given an integer array nums, compute the length of the longest strictly increasing subsequence and reconstruct one valid subsequence. Aim for an O(n log n) algorithm with O(n) space; explain the data structures used and why the approach is correct. c) Grid path (inspired by a well-known problem): Given an m × n grid of integers, find the length of the longest path that is strictly increasing, where each move goes to one of the four orthogonal neighbors (up, down, left, right). Optionally return one such path. Assume 1 ≤ m, n ≤ 500. Design the algorithm and analyze time and space complexity, detailing how you avoid revisiting states and ensure correctness.

Quick Answer: Solve increasing sequence and path problems evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Longest Strictly Increasing Contiguous Subarray

Given an integer array `nums`, find the longest strictly increasing CONTIGUOUS subarray (every element must be greater than the one immediately before it and the elements must be adjacent in the array). Return a list `[length, start, end]` where `length` is the length of the longest such subarray and `start`, `end` are the inclusive indices of one such subarray. Tie-breaking: when multiple subarrays share the maximum length, return the LEFTMOST one (smallest start index). For an empty array, return `[0, -1, -1]`. Example: `nums = [1, 2, 1, 2, 3]` -> `[3, 2, 4]` because `[1, 2, 3]` at indices 2..4 is the longest strictly increasing run. Target: O(n) time, O(1) extra space.

Constraints

  • 0 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • Strictly increasing means nums[i] > nums[i-1] (equal values break the run)
  • Return [0, -1, -1] for an empty array
  • On ties, return the leftmost (smallest start index) subarray

Examples

Input: ([1, 2, 1, 2, 3],)

Expected Output: [3, 2, 4]

Explanation: The run [1,2,3] at indices 2..4 has length 3, the longest strictly increasing run.

Input: ([],)

Expected Output: [0, -1, -1]

Explanation: Empty array returns the sentinel [0, -1, -1].

Input: ([5],)

Expected Output: [1, 0, 0]

Explanation: A single element is a run of length 1 at index 0.

Input: ([5, 4, 3, 2, 1],)

Expected Output: [1, 0, 0]

Explanation: Strictly decreasing: every run has length 1; leftmost is index 0.

Input: ([1, 2, 3, 4, 5],)

Expected Output: [5, 0, 4]

Explanation: The whole array is one strictly increasing run.

Input: ([1, 2, 3, 1, 2, 3, 4],)

Expected Output: [4, 3, 6]

Explanation: Two runs of length 3 then 4; the run [1,2,3,4] at indices 3..6 is longest.

Input: ([3, 3, 3],)

Expected Output: [1, 0, 0]

Explanation: Equal values are not strictly increasing, so the longest run is length 1, leftmost at index 0.

Input: ([-5, -4, -3, 0, 2],)

Expected Output: [5, 0, 4]

Explanation: Negatives are handled normally; the entire array is strictly increasing.

Hints

  1. Track the start index of the current increasing run. Whenever nums[i] <= nums[i-1], the run breaks and a new run starts at i.
  2. Keep a running best (length, start, end). Update it only when the current run is STRICTLY longer than the best so far — this naturally keeps the leftmost answer on ties.
  3. A single linear pass with a handful of integer variables gives O(n) time and O(1) space.

Longest Strictly Increasing Subsequence (with Reconstruction)

Given an integer array `nums`, compute the length of the longest strictly increasing SUBSEQUENCE (elements need NOT be contiguous, but order is preserved) and reconstruct one valid such subsequence. Return a list `[length, subsequence]` where `length` is the LIS length and `subsequence` is one valid longest strictly increasing subsequence (as a list of values). For an empty array, return `[0, []]`. This reference uses patience sorting (binary search over the tails array) with parent pointers, achieving O(n log n) time and O(n) space. Because multiple LIS may exist, the reconstructed subsequence is the specific one produced by this canonical patience-sorting + parent-pointer procedure. Example: `nums = [10, 9, 2, 5, 3, 7, 101, 18]` -> `[4, [2, 3, 7, 18]]`.

Constraints

  • 0 <= len(nums) <= 2500
  • -10^9 <= nums[i] <= 10^9
  • Strictly increasing: each chosen element must be greater than the previous chosen element
  • Return [0, []] for an empty array
  • Use bisect_left (lower bound) so that duplicates do NOT extend the subsequence

Examples

Input: ([10, 9, 2, 5, 3, 7, 101, 18],)

Expected Output: [4, [2, 3, 7, 18]]

Explanation: LIS length is 4; patience sorting reconstructs [2, 3, 7, 18].

Input: ([],)

Expected Output: [0, []]

Explanation: Empty array has no subsequence.

Input: ([7],)

Expected Output: [1, [7]]

Explanation: A single element forms an LIS of length 1.

Input: ([0, 1, 0, 3, 2, 3],)

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

Explanation: Length 4; one valid LIS reconstructed by the algorithm is [0, 1, 2, 3].

Input: ([7, 7, 7, 7, 7, 7, 7],)

Expected Output: [1, [7]]

Explanation: Equal values cannot extend a strictly increasing subsequence, so LIS length is 1.

Input: ([5, 4, 3, 2, 1],)

Expected Output: [1, [1]]

Explanation: Strictly decreasing input: the longest strictly increasing subsequence is any single element; this canonical procedure yields [1].

Input: ([1, 2, 3, 4, 5],)

Expected Output: [5, [1, 2, 3, 4, 5]]

Explanation: Already sorted ascending: the whole array is the LIS.

Input: ([-2, -1, 0, -3, 5],)

Expected Output: [4, [-2, -1, 0, 5]]

Explanation: Negatives handled normally; [-2, -1, 0, 5] is a length-4 LIS.

Hints

  1. Maintain a 'tails' array where tails_vals[k] is the smallest possible tail value of any strictly increasing subsequence of length k+1. Its length equals the LIS length.
  2. For each value x, binary-search (bisect_left) its position. If it lands at the end, the LIS grew; otherwise it replaces an existing tail, keeping tails minimal for future extension.
  3. To reconstruct, store a parent pointer for each index pointing to the element at the previous tail slot, then walk back from the last element that extended the longest tail and reverse.

Longest Increasing Path in a Matrix (LeetCode 329)

Given an `m x n` grid of integers `matrix`, return the length of the longest path along which values are STRICTLY increasing. From any cell you may move to one of the four orthogonal neighbors (up, down, left, right); you may NOT move diagonally or off the grid, and you may not revisit a cell. For an empty grid, return 0. The reference uses DFS with memoization: cache the longest strictly increasing path starting at each cell. Because moves only go to strictly larger neighbors, the state graph is a DAG and no visited-set is needed — a cell can never appear twice on the same increasing path. This gives O(m*n) time and O(m*n) space. Example: `matrix = [[9,9,4],[6,6,8],[2,1,1]]` -> `4` (the path 1 -> 2 -> 6 -> 9).

Constraints

  • 1 <= m, n <= 500 (return 0 for an empty grid)
  • 0 <= matrix[i][j] <= 2^31 - 1
  • Moves are only to the four orthogonal neighbors and only to strictly larger values
  • Equal-valued neighbors do not extend a path

Examples

Input: ([[9, 9, 4], [6, 6, 8], [2, 1, 1]],)

Expected Output: 4

Explanation: Path 1 -> 2 -> 6 -> 9 has length 4.

Input: ([[3, 4, 5], [3, 2, 6], [2, 2, 1]],)

Expected Output: 4

Explanation: Path 3 -> 4 -> 5 -> 6 has length 4.

Input: ([[1]],)

Expected Output: 1

Explanation: A single cell is a path of length 1.

Input: ([],)

Expected Output: 0

Explanation: Empty grid returns 0.

Input: ([[7, 7], [7, 7]],)

Expected Output: 1

Explanation: All values equal; no strictly increasing move exists, so the longest path is 1.

Input: ([[1, 2, 3, 4, 5]],)

Expected Output: 5

Explanation: A single row strictly increasing left to right has a path of length 5.

Input: ([[5], [4], [3], [2], [1]],)

Expected Output: 5

Explanation: A single column; moving up from bottom 1 -> 2 -> 3 -> 4 -> 5 is length 5.

Input: ([[1, 2], [4, 3]],)

Expected Output: 4

Explanation: Path 1 -> 2 -> 3 -> 4 spiraling through all four cells has length 4.

Hints

  1. Define f(r, c) = length of the longest strictly increasing path that STARTS at cell (r, c). The answer is the max of f over all cells.
  2. f(r, c) = 1 + max(f(neighbor)) over neighbors with a strictly greater value (or 1 if none). Memoize f(r, c) so each cell is computed once.
  3. Because you only ever move to strictly larger values, the recursion graph is a DAG — no explicit visited set is needed and there is no risk of cycles.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Find Shortest Unique Prefixes - Meta (medium)
  • Compute Exclusive Execution Times - Meta (medium)
  • Solve Tree Columns And Maze Variants - Meta (medium)
  • Solve Tree Diameter and Palindromic Counts - Meta (medium)
  • Simulate Monster Team Battles - Meta (hard)