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.

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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: