## Array Manipulation

### July 22, 2016

Our first solution takes O(*n*^{2}) 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(*n*^{2}) 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.

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?