## 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.

Advertisements

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.

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.

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:

JavaScript:

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

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