## Array Manipulation

### July 22, 2016

Our first solution takes O(n2) time: Index through the array from left to right, replacing each element in turn with the minimum to its right, calculated by indexing through the remaining elements:

```(define (min-gt x xs)
(let ((gt (filter (lambda (n) (< x n)) xs)))
(if (null? gt) -1 (apply min gt))))

(define (repl-min-gt xs)
(if (null? xs) (list)
(cons (min-gt (car xs) (cdr xs))
(repl-min-gt (cdr xs)))))

> (repl-min-gt '(8 58 71 18 31 32 63 92 43 3 91 93 25 80 28))
(18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1)```

A better approach works from right to left. Each element is added to a binary search tree as it is encountered, then replaced with its in-order successor; if the element has no in-order successor, it is replaced by -1:

```(define (repl-min-gt xs)
(let loop ((xs (reverse xs)) (t nil) (zs (list)))
(cond ((null? xs) zs)
((succ < t (car xs)) =>
(lambda (x)
(loop (cdr xs) (insert < t (car xs)) (cons x zs))))
(else (loop (cdr xs) (insert < t (car xs)) (cons -1 zs))))))

> (repl-min-gt '(8 58 71 18 31 32 63 92 43 3 91 93 25 80 28))
(18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1)```

This takes average time O(n log n), but has worst-case time O(n2) because the binary search tree may become unbalanced. You could avoid that worst-case possibility by using some kind of balanced search tree, if you like, though we won’t bother.

You can run the program at http://ideone.com/zchd6P, where you will also see the binary search tree functions of a previous exercise.

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?