LeetCode Entry

1493. Longest Subarray of 1's After Deleting One Element

5.07.2023 medium 2023 kotlin

Largest 1..1 subarray after removing one item

1493. Longest Subarray of 1’s After Deleting One Element medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/266

Problem TLDR

Largest 1..1 subarray after removing one item

Intuition

Let’s maintain two pointers for a start and a nextStart positions, and a third pointer for the right border.

  • move start to the nextStart when right == 0
  • move nextStart to start of 1’s

Approach

  • corner case is when all array is 1’s, as we must remove 1 then anyway

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\) add asSequence for it to become \(O(1)\)

Code


fun longestSubarray(nums: IntArray): Int {
    var start = -1
    var nextStart = -1
    return if (nums.sum() == nums.size) nums.size - 1
    else nums.mapIndexed { i, n ->
        if (n == 0) {
            start = nextStart
            nextStart = -1
            0
        } else {
            if (nextStart == -1) nextStart = i
            if (start == -1) start = nextStart
            i - start + (if (start == nextStart) 1 else 0)
        }
    }.max() ?:0
}