Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Longest Turbulent Subarray

Posted on September 3, 2019July 26, 2020 by braindenny

Longest Turbulent Subarray



Similar Problems:

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #dynamicprogramming, #slidingwindow

A subarray A[i], A[i+1], …, A[j] of A is said to be turbulent if and only if:

For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.
That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Example 1:

Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])

Example 2:

Input: [4,8,12,16]
Output: 2

Example 3:

Input: [100]
Output: 1

Note:

  1. 1 <= A.length <= 40000
  2. 0 <= A[i] <= 10^9

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution: dynamic programming
// https://code.dennyzhang.com/longest-turbulent-subarray
// Basic Ideas: dynamic programming
//   Treat each character as the ending point
// Complexity: Time O(n), Space O(1)
func max(x, y int) int {
    if x>y {
        return x
    } else {
        return y
    }
}

func maxTurbulenceSize(A []int) int {
    // dp(i, 0) -> increase
    // dp(i, 1) -> decrease
    incr, dec := 1, 1
    res := 1
    for i:=1; i<len(A); i++ {
        incr2, dec2 := 1, 1
        if A[i-1]<A[i] {
            incr2 = dec+1
        }
        if A[i-1]>A[i] {
            dec2 = incr+1
        }
        incr, dec = incr2, dec2
        res = max(res, incr)
        res = max(res, dec)
    }
    return res
}

  • Solution: sliding window
// https://code.dennyzhang.com/longest-turbulent-subarray
// Basic Ideas: sliding window
//
// Complexity: Time O(n), Space O(1)
func max(x, y int) int {
    if x>y {
        return x
    } else {
        return y
    }
}

func maxTurbulenceSize(A []int) int {
    res := 1
    // A[i...j]
    i := 0
    for j:=1; j<len(A); j++ {
        // move the left
        if A[j] == A[j-1] {
            // restart
            i = j
        } else {
            if j>1 {
                if (A[j-1]-A[j])*(A[j-2]-A[j-1]) > 0 {
                    // not the same sequence
                    i = j-1
                }
            }
        }
        res = max(res, j-i+1)
    }
    return res
}
linkedin
github
slack

Post Views: 0
Posted in MediumTagged #dynamicprogramming, #inspiring, #slidingwindow

Post navigation

LeetCode: Maximize Sum Of Array After K Negations
LeetCode: Minimum Swaps to Group All 1’s Together

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.