0

How to find the difference between the min and max indexes of the same value in an array with one loop with complexity exactly O(N)?

For example, given array A:

[4, 6, 2, 2, 6, 6, 1];

the function returns 4.

RobG
  • 142,382
  • 31
  • 172
  • 209
  • 1
    You'd probably create a map of values with the first and last index, calculating the difference as you go. You could also update the max index difference as you go too. What have you tried? – RobG Jun 05 '17 at 05:26
  • 1
    is the requirement only for time? What about space complexity? – Mμ. Jun 05 '17 at 05:28
  • Please check this link I hop you find solution from this link.[Click Here](https://stackoverflow.com/questions/424800/what-is-the-best-way-to-get-the-minimum-or-maximum-value-from-an-array-of-number) – Hardik Chapla Jun 05 '17 at 06:08
  • Possible duplicate of [What is the best way to get the minimum or maximum value from an Array of numbers?](https://stackoverflow.com/questions/424800/what-is-the-best-way-to-get-the-minimum-or-maximum-value-from-an-array-of-number) – Hardik Chapla Jun 05 '17 at 06:13
  • @HardikChapla—the OP is looking for the biggest distance between equal values, where "distance" is the index of the last occurrence minus the index of the first occurrence of the value. – RobG Jun 05 '17 at 06:15
  • Complexity: · expected worst-case time complexity is O(N); · expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). –  Jun 05 '17 at 06:22

3 Answers3

1

I'd use reduce to remember the first index of each value, then update the last value and maximum spread as I went along, e.g.

var data = [4, 6, 2, 2, 6, 6, 1];

function getMaxIndexSpread(data) {
  return data.reduce(function(acc, value, index) {

    if (value in acc) {
      acc[value].lastIndex = index

    } else {
      acc[value] = {firstIndex: index, lastIndex: index};
    }
    var spread = acc[value].lastIndex - acc[value].firstIndex;

    if (acc.maxSpread < spread) acc.maxSpread = spread;

    return acc;
  }, {maxSpread: 0}).maxSpread;
}

console.log(getMaxIndexSpread(data));

There's likely a funkier way, but this makes sense to me.

var data = [4, 6, 2, 2, 6, 6, 1];

console.log(Math.max(...data.map((v,i) => i - data.indexOf(v))));
RobG
  • 142,382
  • 31
  • 172
  • 209
0
   var arr = [4, 6, 2, 2, 6, 6, 1];
    function test(arr) {
        var resultArr = [];
        arr.map(function (v, i, a) {
            for (var j = arr.length - 1; j >= 0; j--) {
                if (v == arr[j]) {
                    resultArr.push({value: v, result: j - i});
//                    console.log(v+'的折扣值'+(j-i));
                    break;
                }
            }
        })
        resultArr.sort(function (a, b) {
            return b.result - a.result;
        })
        console.log(resultArr[0])
    }
    test(arr);
zj250139644
  • 1
0

Try with Array#filter .filter the array without max and min value .Then find max value in filtered array .... its spread syntax

var data = [4, 6, 2, 2, 6, 6, 1];

function bet(data) {
  return Math.max(...data.filter(a => a != Math.max(...data) && a != Math.min(...data)))
}

console.log(bet(data))
prasanth
  • 22,145
  • 4
  • 29
  • 53
  • How is this supposed to work? Given `[4, 6, 2, 2, 6, 6, 1,4]` this still returns 4 when it should return 7. `Math.max(...data)` and `Math.min(...data)` will return the same value every time, so should only be calculated once. – RobG Jun 05 '17 at 12:04
  • `[4, 6, 2, 2, 6, 6, 1,4]` how its possible return `7` .returning length of the array or height number value .Can you explain – prasanth Jun 05 '17 at 12:10
  • As above: "*the OP is looking for the biggest distance between equal values, where "distance" is the index of the last occurrence minus the index of the first occurrence of the value*", so the biggest distance (if a 4 is put at the end) is between the first 4 and the last, so `7– 0 = 7`. – RobG Jun 05 '17 at 12:13