CodingBat: Java. Array-3, Part I

The Array-3 section on CodingBat only contains 9 exercises, but some of those can be quite intricate. My solutions should be fairly easy to follow. If something is unclear, then take a piece of paper, write down a few sample arrays, and trace the execution by hand. With array-based problems, this can be a good preliminary step before staring to write code.

All solutions were successfully tested on 10 March 2013.

maxSpan:

public int maxSpan(int[] nums) {
	if (nums.length > 0) {
		int maxSpan = 1;
		for (int i = 0; i < nums.length; i++)
			for (int j = nums.length - 1; j > i; j--)
				if (nums[j] == nums[i]) {
					int count = (j - i) + 1;
					if (count > maxSpan) maxSpan = count;
					break;
				}
		return maxSpan;
	} else return 0;
}

In line 7 count gets increased by 1 because the span is inclusive of the last element. If the array is empty, the return value is 0.

fix34:

public int[] fix34(int[] nums) {
	for (int i = 0; i < nums.length; i++)
		if (nums[i] == 3) {
			int temp = nums[i + 1];
			nums[i + 1] = 4;
			for (int j = i + 2; j < nums.length; j++)
				if (nums[j] == 4) nums[j] = temp;
		}
	return nums;
}

fix45:

public int[] fix45(int[] nums) {
	for (int i = 0; i < nums.length; i++)
		if (nums[i] == 5 && i == 0
			|| nums[i] == 5 && nums[i - 1] != 4) {
			int pos5 = i;
			for (int j = 0; j < nums.length; j++)
				if (nums[j] == 4 && nums[j + 1] != 5) {
					int temp = nums[j + 1];
					nums[j + 1] = 5;
					nums[pos5] = temp;
					break;
				}
	}
	return nums;
}

canBalance:

public boolean canBalance(int[] nums) {
	for (int i = 0; i < nums.length; i++) { 
		int sum = 0;
		for (int j = 0; j < i; j++) sum += nums[j];
		for (int j = i; j < nums.length; j++) sum -= nums[j];
		if (sum == 0) return true;
	}
	return false;
}

The variable i indicates where the array is split.

linearIn:

public boolean linearIn(int[] outer, int[] inner) {
	int indexInner = 0;
	int indexOuter = 0;
	while (indexInner < inner.length && indexOuter < outer.length) {
		if (outer[indexOuter] == inner[indexInner]) {
			indexOuter++;
			indexInner++;
		} else indexOuter++;
	}
	return (indexInner == inner.length);
}

19 thoughts on “CodingBat: Java. Array-3, Part I

  1. Joseph Bleau

    Hi there!

    I had just completed fix34 and I was looking around to see some other solutions and compare and I came across yours. I was pretty impressed at how short it was compared to mine, tested it, and indeed it passes the tests, but after examining it a bit further it appears to only pass due to a lack of test coverage in all cases, not because the solution is complete.

    The first mistake is at line 5. This will throw an ArrayOutOfBounds exception if there’s a three as the last value of the array. The second confusion is the inner-loop. It appears to set every future element whos current value is four to the current “next value” at your index. This just happens to work out given the tests, but isn’t correct.

    It’s only fair I provide my solution for criticism and discussion as well. Essentially I scan for three’s and four’s. If I encounter a four before I encounter a three I “bank it.” Then upon encountering a three I check the bank for fours. If there is one, I swap the values at those indices. If there are no fours banked, I scan ahead. If I cannot find any fours, I exit early and return the array. If I do find a four I swap them and continue.

    https://gist.github.com/josephbleau/7538450

    Cheers,
    Joseph

    Reply
  2. Joseph Bleau

    Well, it appears I did not read the entire criteria which exempts you from being required to make the checks that I had made in my solution, and so it seems I was a bit too quick to be a bit too ambitious. The site says: “The array contains the same number of 3’s and 4’s, every 3 has a number after it that is not a 3 or 4, and a 3 appears in the array before any 4. ”

    Apologies! Your solution is just fine for the given criteria.

    Joseph

    Reply
    1. Jeff

      I believe your initial assessment that gregor’s solution is flawed was correct. His code does not work for certain test cases, for example, the array {1, 3, 1, 4, 4, 3, 2}. His solution would output {1, 3, 4, 1, 1, 3, 4} , whereas the “correct” output would be something like{1, 3, 4, 2, 1, 3, 4}. My solution is below, would appreciate some feedback.

      public int[] fix34(int[] nums) {
      for (int i = 0; i < nums.length; i++)
      if (nums[i] == 3) {
      int valAfter3 = nums[i+1];
      int indexOf4 = 0;
      for (int j = 0; j < nums.length; j++) {
      if (nums[j] == 4) indexOf4 = j;
      }
      nums[i+1] = 4;
      nums[indexOf4] = valAfter3;
      }
      return nums;
      }

      Reply
  3. Daren Zou

    I also think fix34 on this page is slightly wrong. The problem statement is really confusing. “a 3 appears in the array before any 4” sounds like the 3’s and 4’s alternate appearances in nums. However that’s actually not the case. Based on the 2nd test case I believe “a 3 appears in the array before any 4” just means the first instance of a 3 or a 4 in the array is a 3.

    I believe the above solution to fix34() will fail on this test case (slight modification from 2nd test case on codingbat): {1,3,2,4,4,3,5}.

    Here is my solution:
    public int[] fix34(int[] nums) {
    int indexNext4 = indexNext4(nums, 0);
    for (int i=0; i<nums.length-1; i++) {
    if (nums[i] == 3) {
    nums[indexNext4] = nums[i+1];
    nums[i+1] = 4;
    indexNext4 = indexNext4(nums, indexNext4);
    }
    }
    return nums;
    }

    private int indexNext4(int[] nums, int index) {
    while (index<nums.length-1 && nums[++index]!=4);
    return index;
    }

    Reply
  4. Lei

    We can just use two for-loops, using the first for-loop to check the existence of ‘3’, then remember the index. Then use the second for-loop to search for ‘4’, however the ‘4’ can not be preceded by a ‘3’, then we swap the two elements (element after ‘3’ and ‘4’)

    —-
    public static int[] fix34(int[] nums){
    int threeIdx = 0;
    for (int i = 0; i < nums.length; i++){
    if (nums[i] == 3){
    threeIdx = i;
    for (int j = 0 ; j < nums.length; j++){
    if (nums[j] == 4 && nums[j-1] != 3){
    int temp = nums[i+1];
    nums[i+1] = nums[j];
    nums[j] = temp;
    break;
    }
    }
    i = threeIdx;
    }
    }
    return nums;
    }

    Reply
    1. Gregor Ulm Post author

      Lei,
      what is, in your opinion, the advantage of this solution over the one I’ve posted? All I see is that it is considerably longer.

      Reply
  5. Patryk Dziedzic

    Hello
    Function canBalance can be done without nesting loops:

    public boolean canBalance(int[] nums) {
    int leftSum = 0, rightSum = 0;
    for(int i = 0; i < nums.length; i++)
    rightSum += nums[i];
    for(int i = 0; i < nums.length-1; i++)
    if((leftSum += nums[i]) == (rightSum -= nums[i])) return true;
    return false;
    }

    Reply
  6. S Singh

    Hi,

    It appears that your program passes the 2nd test case by the sheer fact that the test case contains just 1,3,4 and no other integers. It would have failed if the test case were the following for example

    fix34({1, 3, 1, 4, 4, 3, 2})

    Your code will give the following output:

    [1, 3, 4, 1, 1, 3, 4]

    Which is erroneous, the 2 will replaced by a 1 instead of shifting position with the 4..

    The correct output should be:

    [1, 3, 4, 1, 2, 3, 4]

    The following is probably not the most efficient , but it get the job done right.

    public int[] fix34(int[] nums) {

    for(int x=0;x<nums.length;x++){
    if(nums[x] == 3){
    for(int y=x;y<nums.length;y++){
    if( nums[y] == 4)
    {
    int temp= nums[x+1];
    nums[x+1]= 4;
    nums[y]= temp;
    x++;
    break;
    }
    }
    }
    else if(nums[x]==4){
    for(int y=x;y<nums.length;y++){
    if( nums[y] == 3) {
    int temp= nums[y+1];
    nums[x]= temp;
    nums[y+1]= 4;
    x++;
    break;
    }
    }
    }
    }
    return nums;

    }

    Reply
    1. Gregor Ulm Post author

      Thanks for pointing this out. However, if I were to rewrite my solution, I would simply traverse the array twice, in non-nested loops. First, to figure out the values and positions of the integers that have to be moved, as well as the positions of the 4s. Then, a second loop performs the replacement operations.

      Reply
    2. aureus

      Up, I was also curious how this passed the test since the second(third….) Four could be in front of its corresponding 3. It so happens that both numbers that needs to be replace after 3 are 1s.

      Reply
  7. Jeremy

    A readable and efficient solution for fix34() *in my opinion:

    public int[] fix34(int[] nums) {
    ArrayList threes = new ArrayList();
    ArrayList fours = new ArrayList();
    for (int i = 0; i < nums.length; i++) {
    if (nums[i] == 3) threes.add(i+1); // "every 3 has a number after it"
    else if (nums[i] == 4) fours.add(i);
    }
    while (! threes.isEmpty()) { // "contains the same number of 3's and 4's"
    nums[fours.get(0)] = nums[threes.get(0)];
    nums[threes.get(0)] = 4;
    fours.remove(0); threes.remove(0);
    }
    return nums;
    }

    Reply
    1. Jeremy

      I also wanted to post my fix45() problem as it leads on from the fix34() problem.

      public int[] fix45(int[] nums) {
      ArrayList fours = new ArrayList();
      ArrayList fives = new ArrayList();
      for (int i = 0; i < nums.length; i++) {
      if (nums[i] == 4) fours.add(i+1);
      else if (nums[i] == 5) fives.add(i);
      }
      while (! fours.isEmpty()) {
      if (fours.get(0) == fives.get(0)) { fives.remove(0); fours.remove(0); }
      else if (nums[fours.get(0)] == 5) fours.remove(0);
      else {
      nums[fives.get(0)] = nums[fours.get(0)];
      nums[fours.get(0)] = 5;
      fours.remove( 0);
      fives.remove(0);
      }
      }
      return nums;
      }

      Reply
  8. Stefan

    public int[] fix34(int[] nums) {
    int index = 0;
    int change = 0;
    int array[] = find4(nums);
    for(int i = 0;i<nums.length;i++){
    if(nums[i]==3){
    change = nums[i+1];
    nums[i+1]=4;
    nums[array[index++]]=change;
    }
    }
    return nums;
    }

    private int[] find4(int nums[]){
    int counter = 0;
    for(int i = 0;i<nums.length;i++){
    if(nums[i]==4){
    counter++;
    }
    }
    int array[] = new int[counter];
    int index = 0;
    for(int i = 0;i<nums.length;i++){
    if(nums[i]==4){
    array[index++]=i;
    }
    }
    return array;
    }

    Reply
  9. Stefan

    public boolean linearIn(int[] outer, int[] inner) {
    for(int i = 0;i<inner.length;i++)
    if( Arrays.binarySearch(outer,inner[i])<0)
    return false;
    return true;
    }

    Reply
  10. Stefan

    public int[] fix45(int[] nums) {
    int index = 0;
    int array[] = getItems(nums);
    int result[] = new int[nums.length];
    for(int i = 0;i<nums.length;i++)
    if(nums[i]==4)
    result[i]=nums[i];
    for(int i = 0;i<nums.length;i++){
    if(result[i]==4)
    result[i+1]=5;
    if(result[i]==0)
    result[i]=array[index++];
    }
    return result;
    }

    private int[] getItems(int nums[]){
    int counter = 0;
    for(int i = 0;i<nums.length;i++){
    if(nums[i]!=5 && nums[i]!=4){
    counter++;
    }
    }
    int array[] = new int[counter];
    int index = 0;
    for(int i = 0;i<nums.length;i++){
    if(nums[i]!=4 && nums[i]!=5){
    array[index++]=nums[i];
    }
    }
    return array;
    }

    Reply
  11. Stefan

    public int maxSpan(int[] nums) {
    int max = nums.length-1;
    int min = 0;
    for(int i =0 ;i<nums.length;i++){
    if(nums[i]==nums[max]){
    min = i;
    break;
    }
    if(max-i==1)
    max–;
    }
    return max-min+1;
    }

    Reply
  12. Ambarish

    Hi Gregor,

    Here is my maxSpan solution with linear time.

    public int maxSpan(int[] nums) {
    int maxSpan = 0;
    HashMap map = new HashMap();
    for (int i = 0; i < nums.length; i++) {
    if (map.containsKey(nums[i])) {
    int temp = i – map.get(nums[i]) + 1;
    maxSpan = Math.max(maxSpan, temp);
    } else {
    map.put(nums[i], i);
    if (maxSpan == 0) {
    maxSpan = 1;
    }
    }
    }
    return maxSpan;
    }

    Please post if you have linear time solution with constant space.

    Thanks.

    Reply
  13. Ambarish

    Here is my fix34 solution with linear time

    public int[] fix34(int[] nums) {
    int[] res = new int[nums.length];
    int j = 0;

    for (int i = 0; i < nums.length; i++) { // to fix 3's and 4's
    if (nums[i] == 3) {
    res[i] = 3;
    res[i + 1] = 4;
    i++;
    }
    }

    for (int i = 0; i < nums.length; i++){ //populate rest of the elements
    if (nums[i] == 3 || nums[i] == 4) continue;
    if (res[j] == 0) {
    res[j] = nums[i];
    j++;
    } else {
    j = j + 2;
    i–;
    }
    }
    return res;
    }

    Thanks.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Spammer prevention; the answer is an integer: * Time limit is exhausted. Please reload CAPTCHA.