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.
Programming Praxis 
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
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))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:
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:
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]<<",";
}
}
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) }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]I left out a curly brace after ‘return replace;’
And ‘val’ as a parameter to the ‘map’ method…..why cant i edit my comment?