Question 198463 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript: change function from On^2 to On – find integers between identical integers in array

https://jsfiddle.net/4x0cudv7/

// Write a function that returns integers between identical integers
var input = [2, 3, 4, 2, 3, 5, 2]
// output = [3, 4, 4, 2, 3, 5]

const identical = (input) => {
  let returnValue = [];
  
  for (var i=0; i<input.length; i++ ) {
    for (var j=i+1; j<input.length; j++ ) {
        if (input[i] === input[j]) {
        returnValue = returnValue.concat(input.slice(i+1, j));
        j = input.length;
      }
    }
  }
    return returnValue
}

console.log(identical(input));

I have been staring at this and cannot figure out a data type that will let me solve this with a single walk through of the array. Any help would be appreciated.

This was a coding exercise I encountered and could only figure it out for On^2.

Tags:

2

Answers


  1. 0

    You could use an object for seen values and store values in previous seen keys. If key is seen again, the store items ar added to the result set.

    [2, 3, 4, 2, 3, 5, 2]  
    3  4
       4  2
             3  5

    const
    input = [2, 3, 4, 2, 3, 5, 2],
    open = {},
    result = [];

for (const value of input) {
    result.push(...(open[value] || []));
    Object.values(open).forEach(a => a.push(value));
    open[value] = [];
}

console.log(...result);

    Another approach by storing indices.

    const
    input = [2, 3, 4, 2, 3, 5, 2],
    open = {},
    result = [];

for (let i = 0; i < input.length; i++) {
    const value = input[i];
    if (input[open[value]] === value) {
        while (++open[value] < i) result.push(input[open[value]]);
    }
    open[value] = i;
}

console.log(...result);
    Login or Signup to reply.
  2. 0

    Unless you have some element of context to share (for example that the values of the array are among a very restricted set of possibilities ; or that you are mentioning "average case scenario" which some hint on how those number are, randomly, but according to a known stochastic distribution, chosen), in absence of such knowledge, so, the answer is "can’t be done".

    Very concrete argument: let’s consider the case where input contains [1,2,3,...,n,1,2,3,...,n].

    So, input size is 2n.

    And output in this case is size n×(n-1).
    Or, if you prefer, calling N the size of input (N=2n ⇒ n=N/2), output size has len N/2×(N/2-1). Which is O(n²).

    Any algorithm producing such an output has to be at least O(n²), just for its fabrication.

    Maybe, with another data structure for output, for example, one that list slices of input, by referring not the values, but the boundaries, it can be possible. Not even sure of that. For example, keeping a list of potential starting/ending point would need to search in this list, which can’t be done in O(1), unless you index an array with the data itself, or a given unique-hash of this data; but can’t count on that without knowing constraint on the possible value of the data. But well, maybe there is an algorithm I am not aware of that could list the slices in O(n).

    So if the objective was just to list the slice, my proof that O(n²) is the minimum wouldn’t stand (which wouldn’t proof that it is possible to do better. Just that there is no proof that it is impossible).

    But in the meantime, what you’ve asked for, is an algorithm that returns an array of the numbers enclosed in identical numbers. That can’t be done in less than O(n²), in absence of more knowledge on the input.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search