LeetCode in Kotlin

3288. Length of the Longest Increasing Path

Hard

You are given a 2D array of integers coordinates of length n and an integer k, where 0 <= k < n.

coordinates[i] = [xi, yi] indicates the point (xi, yi) in a 2D plane.

An increasing path of length m is defined as a list of points (x1, y1), (x2, y2), (x3, y3), …, (xm, ym) such that:

• xi < xi + 1 and yi < yi + 1 for all i where 1 <= i < m.
• (xi, yi) is in the given coordinates for all i where 1 <= i <= m.

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

Example 1:

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

Output: 3

Explanation:

(0, 0), (2, 2), (5, 3) is the longest increasing path that contains (2, 2).

Example 2:

Input: coordinates = [[2,1],[7,0],[5,6]], k = 2

Output: 2

Explanation:

(2, 1), (5, 6) is the longest increasing path that contains (5, 6).

Constraints:

• 1 <= n == coordinates.length <= 105
• coordinates[i].length == 2
• 0 <= coordinates[i][0], coordinates[i][1] <= 109
• All elements in coordinates are distinct.
• 0 <= k <= n - 1

Solution

import java.util.ArrayList
import java.util.Comparator

class Solution {
    fun maxPathLength(coordinates: Array<IntArray>, k: Int): Int {
        val upper: MutableList<IntArray> = ArrayList<IntArray>()
        val lower: MutableList<IntArray> = ArrayList<IntArray>()
        for (pair in coordinates) {
            if (pair[0] > coordinates[k][0] && pair[1] > coordinates[k][1]) {
                upper.add(pair)
            }
            if (pair[0] < coordinates[k][0] && pair[1] < coordinates[k][1]) {
                lower.add(pair)
            }
        }
        upper.sortWith(
            Comparator { a: IntArray, b: IntArray ->
                if (a[0] == b[0]) {
                    b[1] - a[1]
                } else {
                    a[0] - b[0]
                }
            },
        )
        lower.sortWith(
            Comparator { a: IntArray, b: IntArray ->
                if (a[0] == b[0]) {
                    b[1] - a[1]
                } else {
                    a[0] - b[0]
                }
            },
        )
        return longestIncreasingLength(upper) + longestIncreasingLength(lower) + 1
    }

    private fun longestIncreasingLength(array: List<IntArray>): Int {
        val list: MutableList<Int> = ArrayList<Int>()
        for (pair in array) {
            val m = list.size
            if (m == 0 || list[m - 1] < pair[1]) {
                list.add(pair[1])
            } else {
                val idx = binarySearch(list, pair[1])
                list[idx] = pair[1]
            }
        }
        return list.size
    }

    private fun binarySearch(list: List<Int>, target: Int): Int {
        val n = list.size
        var left = 0
        var right = n - 1
        while (left < right) {
            val mid = (left + right) / 2
            if (list[mid] == target) {
                return mid
            } else if (list[mid] > target) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }
}

This site is open source. Improve this page.