CODEWITHSUNDEEP
arrayssorting
Kunal Chaudhary
Kunal Chaudhary

Reputation: 11

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

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++)

Upvotes: 0

Views: 1123

Answers (2)

RaffleBuffle
RaffleBuffle

Reputation: 5455

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]

Upvotes: 1

nipuna
nipuna

Reputation: 4095

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

Upvotes: 0

Related Questions