Sliding Window

If the window is valid, expand right.
Else, shrink left.

O(n)

Python | Java

	# i
	# nums: [5,7,2,8]
	# j
	def longestWindow(nums: List[int]) -> int:
	j = 0, ans
	for i in range(nums):
	# code using nums[i] to update the state
	# that might invalidate the window
	while invalid():
	# code using nums[j] to update the state
	# and shrink the left edge while the window is invalid
	j += 1
	# longest window so far = len([i, j])
	ans = max(ans, i - j + 1);
	return ans

view raw longestWindow-shrinkable.py hosted with ❤ by GitHub

	// i
	// nums: [5,7,2,8]
	// j
	int longestWindow(int[] nums) {
	int max;
	for (int i = 0, j = 0; i < nums.length; i++) {
	// code using nums[i] to update the state
	// that might invalidate the window
	for (; invalid(); j++) {
	// code using nums[j] to update the state
	// and shrink the left edge while the window is invalid
	}
	// longest window so far = length([i, j])
	max = max(ans, i - j + 1);
	}
	return max;
	}

view raw longestWindow-shrinkable.java hosted with ❤ by GitHub

Maintain a valid window at the end of each outer for loop
to find the longest subsequence.

LeetCode

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

Python | Java

	def longestSubarray(self, nums: List[int]) -> int:
	j = ans = zero = 0
	for i in range(len(nums)):
	if nums[i] == 0: zero += 1
	while zero > 1:
	if nums[j] == 0: zero -= 1
	j += 1
	ans = max(ans, i - j)
	return ans

view raw longestSubarray.py hosted with ❤ by GitHub

	public int longestSubarray(int[] nums) {
	int max = 0, zero = 0;
	for (int i = 0, j = 0; i < nums.length; i++) {
	if (nums[i] == 0) zero++;
	while (zero > 1) {
	if (nums[j++] == 0) zero--;
	}
	max = Math.max(max, i - j);
	}
	return max;
	}

view raw longestSubarray.java hosted with ❤ by GitHub

• Relevant Problems

  https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

  https://leetcode.com/problems/search-insert-position/

  https://leetcode.com/problems/check-if-a-number-is-majority-element-in-a-sorted-array/

  https://leetcode.com/problems/first-bad-version/

  https://leetcode.com/problems/find-smallest-letter-greater-than-target/

  https://leetcode.com/problems/sqrtx/

  https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

  https://leetcode.com/problems/random-pick-with-weight/

  https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

  https://leetcode.com/problems/koko-eating-bananas/

  https://leetcode.com/problems/split-array-largest-sum/

  https://leetcode.com/problems/divide-chocolate/

  https://leetcode.com/problems/missing-element-in-sorted-array/