## Array Manipulation

### July 22, 2016

Our task today comes from Geeks for Geeks:

Given an array of positive integers, replace every element with the least greater element to its right. If there is no greater element to its right, replace it with -1. For instance, given the array [8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28], the desired output is [18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1].

Your task is to write the program that manipulates an array as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 9 Responses to “Array Manipulation”

1. Zack said

Cool exercise! Here is my take on it:

function manipulate{T x[i])

if length(f) == 0
z[i] = -1
else
z[i] = minimum(y[f])
end
end

return z
end

2. Paul said

In Python using the bisect module. I played around with a balanced search tree (in pure Python), but this runs slower than the bisect module.

from bisect import bisect_right, insort

def man(seq):
rev = reversed(seq)
seen, result = [next(rev)], [-1]
for e in rev:
index = bisect_right(seen, e)
result.append(-1 if index == len(seen) else seen[index])
insort(seen, e)
return list(reversed(result))

3. Daniel said

Here’s a solution in Java that loops over the array in reverse, building a binary search tree and updating the values in-place with the least greater element already seen (or -1 if not seen). This has better average runtime complexity than a quadratic brute-force solution. It can be improved by keeping the tree balanced.

My quick-and-dirty binary search tree implementation was written particularly for this problem, which is why it only supports ‘insert’ and returns the value of the successor on insertion.

public class ArrayManipulation {
private static class BinarySearchTree {
private static class Node {
int data;
Node left;
Node right;
}
Node root = null;
public int insert(int value) {
Node node = new Node();
node.data = value;

if (root == null) {
root = node;
return -1;
}

Node current = root;
Node successor = current.right;
while (true) {
if (value == current.data) {
break;
} else if (value < current.data) {
successor = current;
if (current.left == null) {
current.left = node;
break;
}
current = current.left;
} else {
if (successor == current) successor = current.right;
if (current.right == null) {
current.right = node;
break;
}
current = current.right;
}
}

return successor == null ? -1 : successor.data;
}
}

private static void ReplaceLeastGreaterRight(int[] array) {
BinarySearchTree bst = new BinarySearchTree();
for (int i = array.length – 1; i >= 0; –i) {
array[i] = bst.insert(array[i]);
}
}

public static void main(String[] args) {
int[] array = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28};
ReplaceLeastGreaterRight(array);
System.out.println(Arrays.toString(array));
}
}

Here’s the output:

[18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1]

4. Daniel said

Let me try that again. I think I pasted curly quotes in the sourcecode lang, which may not have worked.

Here’s a solution in Java that loops over the array in reverse, building a binary search tree and updating the values in-place with the least greater element already seen (or -1 if not seen). This has better average runtime complexity than a quadratic brute-force solution. It can be improved by keeping the tree balanced.

My quick-and-dirty binary search tree implementation was written particularly for this problem, which is why it only supports ‘insert’ and returns the value of the successor on insertion.

public class ArrayManipulation {
private static class BinarySearchTree {
private static class Node {
int data;
Node left;
Node right;
}
Node root = null;
public int insert(int value) {
Node node = new Node();
node.data = value;

if (root == null) {
root = node;
return -1;
}

Node current = root;
Node successor = current.right;
while (true) {
if (value == current.data) {
break;
} else if (value < current.data) {
successor = current;
if (current.left == null) {
current.left = node;
break;
}
current = current.left;
} else {
if (successor == current) successor = current.right;
if (current.right == null) {
current.right = node;
break;
}
current = current.right;
}
}

return successor == null ? -1 : successor.data;
}
}

private static void ReplaceLeastGreaterRight(int[] array) {
BinarySearchTree bst = new BinarySearchTree();
for (int i = array.length - 1; i >= 0; --i) {
array[i] = bst.insert(array[i]);
}
}

public static void main(String[] args) {
int[] array = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28};
ReplaceLeastGreaterRight(array);
System.out.println(Arrays.toString(array));
}
}

Here’s the output:

[18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1]

5. AMAAS said

My Rough Idea

using namespace std;
#include
#include
main()
{
int arr1[]={8,58,71,18,31,32,63,92,43,3,91,93,25,80,28};
bool m=true;
int q=0;
int g=0;
int minimum=0;

for(int i=0;i<14;i++)
{ int arr2[15];

int count=0;
q=0;
for(int j=i+1;jarr1[i])
{
count++;
arr2[q++]=arr1[j];
}
}

minimum = arr2[0];
for(int r=1;r<count;r++)
{

if(arr2[r]<minimum)
{
minimum=arr2[r];
//g=arr2[w];
}

}

arr1[i]=minimum;

}

arr1[11]=-1;
arr1[13]=-1;
arr1[14]=-1;

for(int i=0;i<15;i++)
{
cout<<arr1[i]<<",";
}

}

6. catalinc said

O(n^2) solution in Golang:

package main

import "fmt"

func leastGreater(a []int, i int) int {
res := -1
for j := i + 1; j < len(a); j++ {
if a[j] > a[i] && (a[j] < res || res == -1) {
res = a[j]
}
}
return res
}

func solve(a []int) []int {
res := make([]int, len(a))
for i := 0; i < len(a); i++ {
res[i] = leastGreater(a, i)
}
return res
}

func main() {
a := []int{8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28}
r := solve(a)
fmt.Printf("%v\n", r)
}

7. kodejuice said

JavaScript:

function arraManip(arr){
var replace = arr.map(function(){
var right = [];

for(var i=0;i<arr.length;i  ){
if(i <= idx) continue;
else if(arr[i] > val) right.push(arr[i]);
}

return (right.length===0)?-1: Math.min.apply(this, right);
});

return replace;
}

var res = arrayManip([8,58,71,18,31,32,63,92,43,3,91,93,25,80,28]);

console.log(res); //=>  [18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1]

8. kodejuice said

I left out a curly brace after ‘return replace;’

9. kodejuice said

And ‘val’ as a parameter to the ‘map’ method…..why cant i edit my comment?