Length of the Longest Increasing Path - Practice Coding Problems

Length of the Longest Increasing Path - Problem

You are given a 2D array of integers coordinates of length n and an integer k, where 0 <= k < n. coordinates[i] = [x_i, y_i] indicates the point (x_i, y_i) in a 2D plane.

An increasing path of length m is defined as a list of points (x_1, y_1), (x_2, y_2), (x_3, y_3), ..., (x_m, y_m) such that:

x_i < x_{i+1} and y_i < y_{i+1} for all i where 1 <= i < m
(x_i, y_i) is in the given coordinates for all i where 1 <= i <= m

Return the maximum length of an increasing path that contains coordinates[k].

Input & Output

Example 1 — Basic Increasing Path

$ Input: coordinates = [[1,1],[2,3],[4,2],[5,4]], k = 0

› Output: 3

💡 Note: Starting from coordinates[0] = (1,1), we can form path (1,1) → (2,3) → (5,4) with length 3

Example 2 — Middle Point

$ Input: coordinates = [[1,1],[2,3],[4,2],[5,4]], k = 1

› Output: 2

💡 Note: Starting from coordinates[1] = (2,3), we can form path (2,3) → (5,4) with length 2

Example 3 — Single Point

$ Input: coordinates = [[3,4]], k = 0

› Output: 1

💡 Note: Only one point exists, so maximum path length is 1

Constraints

1 ≤ coordinates.length ≤ 10³
0 ≤ k < coordinates.length
coordinates[i].length == 2
-10⁴ ≤ coordinates[i][0], coordinates[i][1] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Points

Given coordinates and target index k

Find Paths

Explore all increasing paths from coordinates[k]

Output

Return maximum path length found

Key Takeaway

🎯 Key Insight: Use dynamic programming to efficiently calculate the longest increasing path from each point, avoiding redundant calculations through memoization

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is to use dynamic programming with memoization to find the longest increasing path starting from each point. We recursively explore all valid next points where both x and y coordinates are strictly greater. Best approach is DP with memoization. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sort + Binary Search Optimization	O(n²)	O(n)	Sort points by x-coordinate and use binary search for optimization
Dynamic Programming	O(n²)	O(n)	Use DP to calculate longest increasing path from each point
Brute Force DFS	O(2^n)	O(n)	Try all possible paths from each point using DFS

Sort + Binary Search Optimization — Algorithm Steps

Sort points by x-coordinate while keeping track of original indices
For target point, find longest increasing subsequence in both directions
Combine results to get maximum path length through the target point

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Points

Sort points by x-coordinate to optimize search

Binary Search

Use binary search to find valid y-coordinates

Calculate Path

Build longest increasing path efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int memo[1000];
int coords[1000][2];
int n;

int max(int a, int b) {
    return a > b ? a : b;
}

int getLIS(int startIdx) {
    if (memo[startIdx] != -1) return memo[startIdx];
    
    int result = 1;
    int x = coords[startIdx][0], y = coords[startIdx][1];
    
    for (int i = 0; i < n; i++) {
        if (i != startIdx) {
            int nx = coords[i][0], ny = coords[i][1];
            if (nx > x && ny > y) {
                result = max(result, 1 + getLIS(i));
            }
        }
    }
    
    memo[startIdx] = result;
    return result;
}

int solution(int coordinates[][2], int size, int k) {
    n = size;
    for (int i = 0; i < n; i++) {
        coords[i][0] = coordinates[i][0];
        coords[i][1] = coordinates[i][1];
        memo[i] = -1;
    }
    return getLIS(k);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int k;
    scanf("%d", &k);
    
    int coordinates[1000][2];
    int count = 0;
    char* ptr = line + 1;
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            coordinates[count][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            coordinates[count][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            count++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(coordinates, count, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Sorting takes O(n log n), but we still need O(n²) for DP calculations

⚠ Quadratic Growth

Space Complexity

O(n)

Additional arrays for sorted indices and DP values

⚡ Linearithmic Space

26.3K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort + Binary Search Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler