CODEWITHSUNDEEP
javascriptalgorithmdata-structurestime-complexity
interstellar
interstellar

Reputation: 93

Longest decrease subsequence subarray in Javascript

I encountered this question:

Find longest decrease sequence in an array

So basically, if [3,1,4,3,2,1,2,3] is given, it will return [4,3,2,1] as the longest sequence within it. I was able to solve this question with O(n^2) time complexity but I feel like I can do O(n).

I know I am probably making a giant logic mistake but this is how I approach with 2 pointers method. 

function findDecreaseSubArray(arr) {
  let subList = [arr[0]];
  // let maxLength= 0;
  let left = 0;

  for (let right = 1; right < arr.length; right++) {
    // maxLength = (maxLength, windowEnd - windowStart + 1);

    if (arr[left] > arr[right]) {
      subList.push(arr[right]);
    }else{
      subList.shift();
      left = right-1;
    }
  }
}

What I am trying to accomplish is moving left and right pointers if left element is larger than right, and if so, push both elements into sublist array.

My brain starts giving 404 error after this, so there are 2 subarrays that are decreasing, one of them is [3,1] and the other one is [4,3,2,1].

How could I track one subarray is larger than the other subarray? Or there is a better way to approach this solution?

Any hints, hands, code snippet would highly appreciated. (And sorry about my code snippet, I know it is shitty but I just wanted to display some of my thoughts on code)

Upvotes: 1

Views: 423

Answers (5)

Redu
Redu

Reputation: 26191

This looks like a reducing job.

var a =  [3,1,4,3,2,1,2,3],
    r = a.reduce( function(r,e){
                    var l = r[r.length-1];
                    return l[l.length-1] > e ? ( l.push(e)
                                               , r
                                               )
                                             : ( r.push([e])
                                               , r
                                               );
                  }
                , [[]]
                )
         .reduce((p,c) => p.length > c.length ? p : c);
console.log(r);

Upvotes: 0

TKoL
TKoL

Reputation: 13912

You just have to iterate over the array once, but keep track of the start and length of the longest sequence as you progress through it:

var arr = [3,1,4,3,2,1,2,3];

function findDecreaseSubArray(arr) {
  let startIndex = 0;
  let length = 1;

  let longestSequence = {
    startIndex: 0,
    length: 1
  }

  arr.forEach((element, index, arr) => {
    if (index === 0) return;

    if (element < arr[index -1]) {
      length += 1;
    } else {      
      length = 1;
      startIndex = index;
    }

    if (length > longestSequence.length) {
        longestSequence.length = length;
        longestSequence.startIndex = startIndex;
    }

  })

  return longestSequence;
}

console.log(findDecreaseSubArray(arr));

Upvotes: 3

Nina Scholz
Nina Scholz

Reputation: 386680

This approach supports VLAZ's comment and uses only the indices of the array.

function longestDecreasing(array) {
    var longest,
        start = 0,
        i;

    for (i = 0; i < array.length; i++) {
        if (!i || array[i] < array[i - 1]) continue;
        if (!longest || longest[1] - longest[0] < i - start) longest = [start, i];
        start = i;
    }

    return array.slice(...longest && longest[1] - longest[0] > i - start
        ? longest
        : [start, i]);
}

console.log(longestDecreasing([3, 1, 4, 3, 2, 1, 2, 3]))

Upvotes: 2

CHANist
CHANist

Reputation: 1412

Here is my code. 

function getLongestDecreaseSequence(arr) {
  if (
    Object.prototype.toString.call(arr) !== "[object Array]" ||
    arr.length == 0
  ) {
    return arr;
  }

  let longestArr = [];
  let tmpArr = [],
    lastTmpIndex = -1;

  arr.forEach((value, i) => {
    if (arr[lastTmpIndex] < value) {
      tmpArr = [];
    }
    // no matter what, I will put it in tmpArray
    lastTmpIndex = i;
    tmpArr.push(value);

    if (longestArr.length < tmpArr.length) {
      longestArr = tmpArr;
    }
  });
  return longestArr;
}

console.log(getLongestDecreaseSequence([3, 1, 4, 3, 2, 1, 2, 3]));

Upvotes: 0

CertainPerformance
CertainPerformance

Reputation: 370989

It would probably be easier to iterate normally, from the first index to the end, while pushing sequential sequences to an array, which gets reset when a number greater than the last is found. When resetting, assign the resulting sequence array to a more permanent variable if it's longer than the array in that permanent variable:

const findDecreaseSubArray = (arr) => {
  let longestSoFar = [];
  let currentSequence = [];
  const reset = (newItem) => {
    if (currentSequence.length > longestSoFar.length) {
      longestSoFar = currentSequence;
    }
    currentSequence = [newItem];
  };
  for (const item of arr) {
    if (currentSequence.length && item > currentSequence[currentSequence.length - 1]) {
      reset(item);
    } else {
      currentSequence.push(item);
    }
  }
  reset();
  return longestSoFar;
};
console.log(findDecreaseSubArray([3,1,4,3,2,1,2,3]));

Upvotes: 1

Related Questions