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