how to get substring length of sub array in javascript?

46
June 16, 2019, at 1:40 PM

I am trying to solve this problem but I am not getting the expected output

function solution(A) {
    var start = -1,
        Ay = []
    for (var i = 0; i < A.length; i++) {
        start = i;
        if(A[i] > A[i+1]){
            bool = false;
            for (j = i+1; A.length; j++) {
                if (A[j] > A[j + 1] && bool) {
                    bool = !bool;
                } else if (A[j + 1] > A[j] && !bool) {
                    bool = !bool;
                } else {
                    A.push([start, j])
                    break;
                }
            }
        }else {
            bool = true;
            for (j = i+1; A.length; j++) {
                if (A[j] > A[j + 1] && bool) {
                    bool = !bool;
                } else if (A[j + 1] > A[j] && !bool) {
                    bool = !bool;
                } else {
                    Ay.push([start, j])
                    break;
                }
            }
        }
    }
    console.log(A);
}
solution([9,4,2,10,7,8,8,1,9])

Your team is analysing a flight plane. Your task is to find the longest period of turbulence.

The height of the plane above the ground is measured once every second of th flight. The measurement on K-th second is recoreded as an integer A[K].

Security regulations decree that a period of time is considered to be turbulence if changes in measured heights alternate: for example, if the plane went up, then down, then up and so on.

Most precisely, period (P,Q) is considered to be an turbulence if:

A[P] > A[P+1] < A[P+2] > ..., and so on, up to A[Q] or A[P] < A[P+1] > A[P+2] < ..., and so on, up to A[Q] Note that, for definition, if P = Q then the period is also considered to be turbulence.

Write a function:

def solution(A)

that, given an array A consisting of N integers representing height measurements during the flight, return the size of the longest period of turbulence in A.

Examples:

Given array A = [9,4,2,10,7,8,8,1,9] the function should return 5, because period (1,5) is considered to be turbulence (A[1] > A[2] < A[3] > A[4] < A[5]). Note that period (1,6) is not turbulence, because A[5] = A[6]. image

Given array A = [4,8,12,16] the function should return 2.(A[1]A[3])

Given array A = [100] the function should return 1.

Given N = 100,000 and A = [50,150,50,150,...,50,150] ([50,150] repeating 50,000 times) the function should return 100,000.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1...100,000]; each element of array A is an integer within the range [1..1,000,000,000].

from here I take a question https://leetcode.com/discuss/interview-question/202838/Turbulence

https://leetcode.com/problems/longest-turbulent-subarray/solution/

Answer 1

var maxTurbulenceSize = function(A) { 
    if(A.length < 3) return A.length == 1 ? 1 : (A[0] == A[1] ? 1 : 2); 
     
    var max_length = 1,cnt = 1; 
    var smaller = false; 
    var prev_equal = true; 
     
    for (var i = 1; i < A.length; i++) { 
        if(A[i] > A[i-1]){ 
            if(prev_equal){ 
                prev_equal = false; 
                cnt++; 
            }else if(smaller){ 
                cnt++; 
            }else{ 
                cnt = 2; 
            } 
            smaller = false; 
        }else if(A[i] < A[i-1]){ 
            if(prev_equal){ 
                prev_equal = false; 
                cnt++; 
            }else if(smaller){ 
                cnt = 2; 
            }else{ 
                cnt++; 
            } 
            smaller = true; 
        }else{ 
            cnt = 1; 
            prev_equal = true; 
        } 
         
        max_length = Math.max(max_length,cnt); 
    } 
     
    return max_length; 
}; 
 
console.log(maxTurbulenceSize([9,4,2,10,7,8,8,1,9]));

  • The problem statement says that the turbulence would need to follow the sequence of either < > < > < > or > < > < > <.

  • If length of the array is < 3, then we return the length itself with an additional check of edge case when length is 2 and both elements are equal. We do this because length of sequence 2 would follow either < or >(although length 1 is considered turbulent which is a bit weird).

  • Now, comparisons happen in terms of what was the previous result and what is our current result. If previous comparison was >, then current should be < or vice-versa.

  • So, we maintain a smaller variable to judge the comparisons. If the current comparison is in alignment with respect to smaller, then we do cnt++, else we reassign cnt = 2 and smaller to whatever current comparison holds. We assign 2 to cnt because since the alignment broke, at least the current and previous one make a new alignment.

  • Tricky part comes to equal elements. We maintain a prev_equal variable for that. if 2 elements are found to be equal, then we assign true to it and make cnt as 1 since previous and current are same elements.

  • When prev_equal == true, we don't know what kind of sequence we would find in the future. It could be <> or ><.

  • So, we take whatever comes our way when prev_equal == true and increase the cnt and future comparisons would again be handled gracefully.

  • Time Complexity: O(n), Space complexity O(1).

Answer 2

Here is my O(n^2) solution. Though i didn't find any clearance for an empty array.

const largeFirstSeries = (arr, index) => { 
    let len = 1; 
    for(let i = index, counter = 0; i < arr.length-1; i++, counter++) { 
        if(counter % 2 == 0 && arr[i] > arr[i+1]) { 
            len++; 
        } else if(counter % 2 !== 0 && arr[i] < arr[i+1]) { 
            len++; 
        } else { 
            return len; 
        } 
    } 
    return len;     
} 
const smallFirstSeries = (arr, index) => { 
    let len = 1; 
    for(let i = index, counter = 0; i < arr.length-1; i++, counter++) { 
        if(counter % 2 == 0 && arr[i] < arr[i+1]) { 
            len++; 
        } else if(counter % 2 !== 0 && arr[i] > arr[i+1]) { 
            len++; 
        } else { 
            return len; 
        } 
    } 
    return len; 
} 
const findTurbulance = (arr) => { 
    let len = 0; 
    let maxLen = 1; 
 
    if(arr.length == 1) return 1; 
 
    for(let i = 0; i < arr.length-1; i++) { 
        if(arr[i] > arr[i+1]) { 
            len = largeFirstSeries(arr, i);             
        } else if(arr[i] < arr[i+1]) { 
            len = smallFirstSeries(arr, i); 
        } 
         
        if(maxLen < len) maxLen = len; 
    } 
    return maxLen; 
     
} 
 
console.log(findTurbulance([9,4,2,10,7,8,8,1,9])) 
console.log(findTurbulance([4,8,12,16])) 
console.log(findTurbulance([100]))

And here is a O(n) solution. I've used two pointer method to solve this. Here this function is doing the turbulent checking.

const isTurbulent = (arr, index) => {
return (arr[index] > arr[index-1] && arr[index] > arr[index+1])
        || (arr[index] < arr[index-1] && arr[index] < arr[index+1])
}

const isTurbulent = (arr, index) => { 
    return (arr[index] > arr[index-1] && arr[index] > arr[index+1]) 
            || (arr[index] < arr[index-1] && arr[index] < arr[index+1]) 
} 
 
const findTurbulance = (arr) => { 
    let arrLen = arr.length; 
    let maxLen = 1; 
    let i = 0; 
    while(i < arrLen-1) {         
        if(arr[i] == arr[i+1]) { 
            i++; 
            continue; 
        } 
        let j = i+1; 
        while(j+1 < arrLen && isTurbulent(arr, j)) { 
            j++; 
        } 
        maxLen = Math.max(maxLen, j - i + 1);         
         
        i = j; 
    } 
    return maxLen; 
} 
console.log(findTurbulance([9,4,2,10,7,8,8,1,9])) 
console.log(findTurbulance([4,8,12,16])) 
console.log(findTurbulance([100]))

READ ALSO
How to order the order of returned API calls with generators?

How to order the order of returned API calls with generators?

I'm practicing some more advanced Javascript techniques, and came across generators and iterators as something I wanted to look intoI know that I'm doing this incorrectly, but I'm not really sure how to go about it

62
Why are elements in 3d rendering at the wrong size only at certain angles of perspective and rotation?

Why are elements in 3d rendering at the wrong size only at certain angles of perspective and rotation?

I'm trying to create a 3d hallway using css and react inline stylesThe function mimics a first-person perspective by translating and rotating the cuboid in relation to mouse position and arrow key inputs

44
How can I create an image overlay blend mode algorithm like on Photoshop?

How can I create an image overlay blend mode algorithm like on Photoshop?

I'm working on a code that should blend 2 images with each otherThe effect should be similar to Photoshop overlay blend mode or screen mode

65
How to print current location using GPS?

How to print current location using GPS?

I want to print current city, state and countryI used IP tracking but that is not much accurate and displaying me different cities, i want current city

54