Finding the sum of nearest smallest and greatest number in an array

Question

The question is straightforward that we want to find the sum of the nearest smallest and greatest number for every index of an array. But the part which I am not able to get is how to return the resulting array with the sum values on the same index values as the numbers.

Example: [1,5,2,3,8]
The sum for each indexes is as follows: 
for index 0 the element is 1 hence sum = (0 + 2) = 2 
since it has no smallest number therefore taking the nearest smallest number to be 0.
similarly for index 1 sum = (3 + 8 ) = 11 {3 - nearest smallest number to 5 and 8 nearest largest number}
and so on.

What I did was sort the given array then iterate through it and in every iteration take the sum of arr[i-1] + arr[i+1] elements and storing them in the result/answer array.{ with 0th and last element being dealt with separately }

So basically

If the input array is -> [1,5,2,3,8]
the resultant array will be -> [2,4,7,11,5]
but it is required to be as -> [2,11,4,7,5]
that is the sum of each index element to be at the same index as was the initial number

(I am using C++)

Can you please specify what "the nearest smallest and greatest number" means? — Stef
– Stef, Commented Jun 2, 2021 at 17:53
In simple word if we sort the elements, the immediate number before the element for which we are finding the above said is the nearest smaller number and the immediate greatest number is the nearest greatest number. — Kunal Chaudhary
– Kunal Chaudhary, Commented Jun 2, 2021 at 17:58

RaffleBuffle · Accepted Answer · 2021-06-02 23:58:46Z

1

The trick is to create an array of indexes into the original array and sort this, rather than sorting the original array.

You don't mention what language you're using, but here's some Java code to illustrate:

Integer[] arr = {1,5,2,3,8};
System.out.println(Arrays.toString(arr));

Integer[] idx = new Integer[arr.length];
for(int i=0; i<idx.length; i++) idx[i] = i;

System.out.println(Arrays.toString(idx));
Arrays.sort(idx, (a, b) -> arr[a] - arr[b]);
System.out.println(Arrays.toString(idx));

Integer[] res = new Integer[arr.length];        
for(int i=0; i<arr.length; i++)
{
    res[idx[i]] = (i > 0 ? arr[idx[i-1]] : 0) + (i < arr.length - 1 ? arr[idx[i+1]] : 0);
}       
System.out.println(Arrays.toString(res));

Or translated into (possibly non-idiomatic) C++ (Ideone):

int len = 5;
array<int, 5> arr{1,5,2,3,8};

for(auto i : arr) cout << i << " ";
cout << endl; 
   
array<int, 5> idx;
for(int i=0; i<len; i++) idx[i] = i;

for(auto i : idx) cout << i << " ";
cout << endl; 
   
sort(idx.begin(), idx.end(), [&arr](int a, int b) {return arr[a] < arr[b];});
   
for(auto i : idx) cout << i << " ";
cout << endl; 
    
array<int, 5> res;
for(int i=0; i<len; i++)
  res[idx[i]] = (i > 0 ? arr[idx[i-1]] : 0) + (i < len - 1 ? arr[idx[i+1]] : 0);
        
for(auto i : res) cout << i << " ";
cout << endl;

Output:

[1, 5, 2, 3, 8]
[0, 1, 2, 3, 4]
[0, 2, 3, 1, 4]
[2, 11, 4, 7, 5]

edited Jun 2, 2021 at 23:58

answered Jun 2, 2021 at 17:50

RaffleBuffle

5,4651 gold badge11 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Kunal Chaudhary Over a year ago

WOW! I had thought of somehow mapping the index of the result to the initial array ,but couldn't really get any concrete idea, thanks for this!(completely forgot that the third parameter of the sort function can be used a s a comparator)

nipuna · Accepted Answer · 2021-06-02 17:53:45Z

You will get the desired output by running this. It is written in Go.

Copy the original input array
Sort the copied array
Create a Map Sorted Value -> Sorted Index
make an output array with same length as input
Iterate through the Input Array and check the value is largest or smallest and Do the Sum as described in the question
store the Sum in the output array in the same index as input array

package main

import (
    "fmt"
    "sort"
)

func main() {
    indexes := []int{1, 5, 2, 3, 8}
    output := findSum(indexes)
    fmt.Println(output)
}

func findSum(input []int) []int {
    if len(input) < 2 {
        return input
    }
    sorted := make([]int, len(input))
    copy(sorted, input)
    sort.Slice(sorted, func(i, j int) bool {
        return sorted[i]< sorted[j]
    })
    sortedMap := make(map[int]int)
    for i, i2 := range sorted {
        sortedMap[i2] = i
    }

    output := make([]int, len(input))
    for j, index := range input {
        i := sortedMap[index]
        if i == 0 {
            output[j] = sorted[i+1]
            continue
        }
        if i == len(input) - 1 {
            output[j] = sorted[i-1]
            continue
        }
        output[j] = sorted[i - 1] + sorted[i + 1]
    }

    return output
}

You can run here

Collectives™ on Stack Overflow

Finding the sum of nearest smallest and greatest number in an array

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related