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/
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)
.
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]))
Python Threads: event.set does not activate the thread in Task/Job management
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
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
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
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