Compact a given array problem

Dont know whether this is a duplicate, but this was an interview question asked to me. Given an array of random numbers and -1 placed inb开发者_Python百科etween, I have to compact the array meaning all the -1s are to be replaced and the final output should be the last valid index with the fresh array. For example.

Input:
3 4 -1 -1 -1 5 8 -1 8
Output:
3 4 5 8 8 5 8 -1 8 and last valid index is 4

Input:
-1 -1 -1 -1 -1 2
Output:
2 -1 -1 -1 -1 2 and last valid index is 0

Input:
-1 -1 -1 3 3 3
Output:
3 3 3 3 3 3 and last valid index is 2

You should not swap the values just the last valid index along with the array is enough to decipher the not -1 values.

---

int K=0
FOR i=0; i<LEN; i++
  IF arr[i]!=-1
      arr[K]=arr[i]
      K++
  END IF
RETURN K-1

---

Something like that ? it's PHP

<?php
    $array = array('3','4','-1','-1','-1','5','8','-1','8');
    $count = count($array);
    $k = 0;
    $i = 0;
    while($i < $count && $k < $count)
    {
        echo $array[$i];
        if($array[$i] == '-1')
        {
            echo '|';
            if ($i>=$k){$k = $i + 1;}
            $found = false;
            while($k < $count && !$found)
            {
                echo 'X';
                if($array[$k] != '-1')
                {
                    $array[$i] = $array[$k];
                    $found = true;
                }
                $k++;
            }
        }    
        $i++;
    }
    print_r($array);
    echo 'Last index'.($i - 1);
?>

---

import java.util.Arrays;

public class Compact {
    static int previousValid(int[] nums, int startIndex) {
        while (--startIndex >= 0 && nums[startIndex] == -1);
        return startIndex;
    }
    static int nextInvalid(int[] nums, int startIndex) {
        while (++startIndex < nums.length && nums[startIndex] != -1);
        return startIndex;
    }
    static void compact(int... nums) {
        int last = previousValid(nums, nums.length);
        for (int h = -1, t = last + 1;
            (h = nextInvalid(nums, h)) < (t = previousValid(nums, t));
        ) {
            nums[last = h] = nums[t];
        }
        System.out.println(Arrays.toString(nums) + "; last valid = " + last);
    }
    public static void main(String[] args) {
        compact(3, 4, -1, -1, -1, 5, 8, -1, 8);
          // "[3, 4, 8, 8, 5, 5, 8, -1, 8]; last valid = 4"    
        compact(-1, -1, -1, -1, -1, 2);
          // "[2, -1, -1, -1, -1, 2]; last valid = 0"    
        compact(-1, -1, -1, 3, 3, 3);
          // "[3, 3, 3, 3, 3, 3]; last valid = 2"           
        compact(-1, -1, -1);
          // "[-1, -1, -1]; last valid = -1"            
        compact(6, 6, 6);
          // "[6, 6, 6]; last valid = 2"
    }
}

Key ideas:

• Use previousValid and nextInvalid helper methods to make logic clearer
• Keep track of h and t for "head" and "tail"
  • h finds nextInvalid
  • t finds previousValid
• Keep assigning nums from index t to h while h < t