Sorting array of ints by the product of each number and its index?‽

Question

I am doing the following programming exercise: Sort an array by value and index. The statement is:

Your task is to sort an array of integer numbers by the product of the value and the index of the positions.

For sorting the index starts at 1, NOT at 0! The sorting has to be ascending. The array will never be null and will always contain numbers.

Example:

Input: 23, 2, 3, 4, 5 Product of value and index: 23 => 23 * 1 = 23 -> Output-Pos 4 2 => 2 * 2 = 4 -> Output-Pos 1 3 => 3 * 3 = 9 -> Output-Pos 2 4 => 4 * 4 = 16 -> Output-Pos 3 5 => 5 * 5 = 25 -> Output-Pos 5

Output: 2, 3, 4, 23, 5

I have tried to use a map where we store the original array's values as keys, and the product of the original ones with its indexes, are the values:

import java.util.*;
import java.util.stream.*;
public class Kata
{
  public static int[] sortByValueAndIndex/**/(int[] array)
  {
    System.out.println("\nArray: "+Arrays.toString(array));
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    for(int i = 0; i < array.length; i++){
      map.put(array[i],array[i]*(i+1));
    }
    System.out.println("map: "+map.toString());
    map = map.entrySet().stream().sorted(Map.Entry.comparingByValue())
          .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
          (e1, e2) -> e1, LinkedHashMap::new));
    System.out.println("sorted map: "+map.toString());          
    return map.keySet().stream().mapToInt(Number::intValue).toArray();
  }
}

It does work for arrays with unique elements, for example for the following tests(extracted from the exercise):

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.util.Arrays;

public class KataTests {
    @Test
    public void exampleTests() {

      int[] actual = Kata.sortByValueAndIndex(new int[] { 1, 2, 3, 4, 5 });
      int[] expected = new int[] { 1, 2, 3, 4, 5 };
      String message = "Your result:\n" + arrayToString(actual) + "\n\nExpected result:\n" + arrayToString(expected) + "\n\n";
      assertEquals(message, arrayToString(expected), arrayToString(actual));

      actual = Kata.sortByValueAndIndex(new int[] { 23, 2, 3, 4, 5 });
      expected = new int[] { 2, 3, 4, 23, 5 };
      message = "Your result:\n" + arrayToString(actual) + "\n\nExpected result:\n" + arrayToString(expected) + "\n\n";
      assertEquals(message, arrayToString(expected), arrayToString(actual));

      actual = Kata.sortByValueAndIndex(new int[] { 26, 2, 3, 4, 5 });
      expected = new int[] { 2, 3, 4, 5, 26 };
      message = "Your result:\n" + arrayToString(actual) + "\n\nExpected result:\n" + arrayToString(expected) + "\n\n";
      assertEquals(message, arrayToString(expected), arrayToString(actual));

      actual = Kata.sortByValueAndIndex(new int[] { 9, 5, 1, 4, 3 });
      expected = new int[] { 1, 9, 5, 3, 4 };
      message = "Your result:\n" + arrayToString(actual) + "\n\nExpected result:\n" + arrayToString(expected) + "\n\n";
      assertEquals(message, arrayToString(expected), arrayToString(actual));
    }

    private String arrayToString(int[] array)
    {
      return Arrays.toString(array);
    }
}

However, when we have as input an array with repeated elements, it raises an exception because of map's keys are uniques so we are omitting some original array's numbers.

For example if input is:

[7, -9, 24, 0, 7, 23, -4, -28, -14, 5, 20, 26, 22, -24]

Current output:

[-24, -28, -14, -4, -9, 0, 7, 5, 24, 23, 20, 22, 26]

Expected one:

[-24, -28, -14, -4, -9, 0, 7, 7, 5, 24, 23, 20, 22, 26]

As we see, using the trace, we observe that the map holds just the product for the last 7, 7*5=35:

Array: [7, -9, 24, 0, 7, 23, -4, -28, -14, 5, 20, 26, 22, -24]

map: {0=0, -4=-28, 5=50, 7=35, -9=-18, -14=-126, 20=220, 22=286, 23=138, -24=-336, 24=72, 26=312, -28=-224}

sorted map: {-24=-336, -28=-224, -14=-126, -4=-28, -9=-18, 0=0, 7=35, 5=50, 24=72, 23=138, 20=220, 22=286, 26=312}

Is there a way to fix this behaviour to allow repeated elements? Do we need to use another data structure other than map? Are there other approaches, like Comparator / Compare, or just using Lists/Arrays?‽

I have also read:

EDIT: As @JB Nizet recommended we can do the following:

import java.util.*;
import java.util.stream.*;
public class Kata
{
  public static int[] sortByValueAndIndex/**/(int[] array)
  {
    ElementWithProduct[] elements = new ElementWithProduct[array.length];
    for(int i = 0; i < elements.length; i++){
      elements[i] = new ElementWithProduct(array[i], array[i]*(i+1));
    }
    Arrays.sort(elements, new Comparator<ElementWithProduct>(){
      public int compare(ElementWithProduct e1, ElementWithProduct e2){
        if(e1.product > e2.product){
          return 1;
        }
        if(e1.product < e2.product){
          return -1;
        }
        return 0;
      }
    });
    for(int i = 0; i < elements.length; i++){
      array[i] = elements[i].value;
    }
    return array;
  }

  public static class ElementWithProduct{
    public int value;
    public int product;

    public ElementWithProduct(int value, int product){
      this.value = value;
      this.product = product;
    }
  }
}

score 1 · Answer 1 · answered Dec 28 '19 at 16:35

Create a List<ElementWithProduct> (or an array of type ElementWithProduct[]), containing objects which contain an element's value, and the product of its value and its index.

Then sort that list or array by product.

Then transform it back to an array of elements.

score 0 · Answer 2 · answered Dec 28 '19 at 16:39

You cannot use a map (unless a map of lists, which for your case I think is not practical), you must use a List/Set of objects with two properties (or use a Sorted List/Set so items are sorted as they are added). If you didn't use a sorted list, use Collections.sort. Finally generate the output list, if needed.

score 0 · Accepted Answer · edited Dec 28 '19 at 20:05

This can be answer. Please try this logic.

public static int[] sortByValueAndIndex(int[] array) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        int temp = array[i] * (i + 1);
        map.put(array[i], temp);
    }

    List<Map.Entry<Integer, Integer>> list = new LinkedList<Map.Entry<Integer, Integer>>(map.entrySet());
    Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
        public int compare(Map.Entry<Integer, Integer> o1,
                           Map.Entry<Integer, Integer> o2) {
            return (o1.getValue()).compareTo(o2.getValue());
        }
    });

    int i = 0;
    for (Map.Entry<Integer, Integer> l : list) {
        result[i] = l.getKey();
        i++;
    }
    return result;
}

suleman · Answer 4 · 2019-12-28T17:39:15.487

you can create Map<Integer,List<Integer>> where you can use TreeMap, implementation of Map Interface, which maintain order. Map key is the product of value and index. Map value is,value of array element, list so if there is any repeating element it just store in the list.

int[] ary ={7, -9, 24, 0, 7, 23, -4, -28, -14, 5, 20, 26, 22, -24};

       Map<Integer, List<Integer>> maps = new TreeMap<>();

       for(int i=1;i<=ary.length;i++){
           Integer pro=i*ary[i-1];
           List<Integer> list2 = new ArrayList<Integer>();
           if(!maps.containsKey(pro)){
               list2.add(ary[i-1]);
               maps.put(pro, list2);
           }
           else{
               maps.get(pro).add(ary[i-1]);
           }

       }
       System.out.println(maps);

Output:

{-336=[-24], -224=[-28], -126=[-14], -28=[-4], -18=[-9], 0=[0], 7=[7], 35=[7], 50=[5], 72=[24], 138=[23], 220=[20], 286=[22], 312=[26]}

score 0 · Answer 5 · answered Dec 28 '19 at 17:22

If you care about sorting algorithms, you can try with count sort

import java.util.Arrays;

public class Kata
{
  public static int[] sortByValueAndIndex/**/(int[] arr)
  {
    int[] product_arr = new int[arr.length];
    for(int i = 0; i < arr.length; i++) {
        product_arr[i] = arr[i] * (i+1);
    }

    int min = Arrays.stream(product_arr).min().getAsInt();
    int max = Arrays.stream(product_arr).max().getAsInt();
    int min_abs = Math.abs(min);
    int range = min_abs + max + 1;
    int[] range_arr = new int[range];
    int[] result = new int[arr.length];

    for(int i : product_arr) {
        range_arr[i + min_abs]++;
    }

    for(int i = 1; i < range; i++ ) {
        range_arr[i] += range_arr[i-1];
    }

    for(int i = 0; i < arr.length; i++) {
        result[range_arr[product_arr[i] + min_abs] - 1] = arr[i];
        range_arr[product_arr[i] + min_abs]--;
    }

    System.out.println(Arrays.toString(result));
  }
}

References: https://www.geeksforgeeks.org/counting-sort/

Sorting array of ints by the product of each number and its index?‽

5 Answers5