CodingBat: Java. Array-3, Part II

squareUp:

public int[] squareUp(int n) {
	int[] result = new int[n * n];
	int pos = 0;

	for (int i = 1; i <= n; i++) {
		for (int k = 1; k <= n - i; k++) result[pos++] = 0;
		for (int j = i; j > 0; j--) result[pos++] = j;
	}
	return result;
}

seriesUp:

public int[] seriesUp(int n) {
	int[] result = new int[n * (n + 1) / 2];
	int pos = 0;
	int i = 1;
	while (i <= n + 1) {
		for (int j = 1; j < i; j++) result[pos++] = j;
		i++;
	}
	return result;
}

maxMirror:

public int maxMirror(int[] nums) {
	int[] numsCopy = new int[nums.length];
	for (int i = nums.length - 1, j = 0; i >= 0; i--, j++)
		numsCopy[j] = nums[i];

	int max = 0;

	for (int i = 0; i < nums.length; i++) {
		int count = 0;
		int pos1 = i;
		int pos2 = 0;
		boolean flag = false;

		while (pos1 < nums.length && pos2 < nums.length) {
			if (!flag) {
				if (nums[pos1] != numsCopy[pos2]) pos2++;
				else {
					flag = true;
					count = 1;
					pos1++;
					pos2++;
				}
			} else {
				if (nums[pos1] == numsCopy[pos2]) {
					count++;
					pos1++;
					pos2++;
				} else {
					if (count > max) max = count;
					pos1 = i;
					flag = false;
				}
			}
			if (count > max) max = count;
		}
	}
	return max;
}

The input array is reversed to make the subsequent steps clearer to follow. This leads to slightly more code, but it should increase comprehensibility.

countClumps:

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

At first I was tempted to use only one for loop and operate with a flag variable. Using a second for loop led to a more elegant solution, though. A neat detail is that the running time is linear since the nested for loop only increases i.

17 thoughts on “CodingBat: Java. Array-3, Part II

  1. Joseph Gabriella

    I can not follow the logic of your code below for the SeriesUp Array 3 problem.
    You begin by declaring i=1. Then, you for statement after declaring j=1, you write j<i as the condition. That means, that initially both j and i = 1, so the condition is not met and the for loop should not execute, right?

    Can you explain what I am missing here?

    int i = 1;
    while (i <= n + 1) {
    for (int j = 1; j < i; j++) result[pos++] = j;
    i++;
    }

    Reply
    1. Gregor Ulm Post author

      It seems you’re disregarding the outer while-loop. Your reasoning is correct when n == 0. In that case the outer while-loop gets executed once, and since j == i, the body of the for-loop won’t be executed.

      However, consider what happens when n > 0. Let’s say n == 1. The condition of the while-loop then becomes “i < = 2". In the first iteration, i == 1 and j == 1, and thus the for-loop won't get executed. However, afterwards the variable i gets incremented by 1. In the second iteration of the while-loop, j again starts at 1, but i == 2, which means that the loop will execute, since in this case i is less than j. The reasoning for n > 1 is similar.

      Does this help?

      Reply
    2. Gregor Ulm Post author

      By the way, Joseph, are you sure you don’t want to explore Haskell instead of Java? The solution is a one-liner in that language:

      seriesUp :: Int -> [Int]
      seriesUp n = concatMap (\x -> [1..x]) [1..n]

      Reply
  2. Kenny

    Hello,Gregor, I try your solution at SeriesUp, because I was freaking out by that problem. But why the Codingbat returned the timed out errors?

    Reply
  3. Stefan

    public int[] seriesUp(int n) {
    int array[] = new int[n*(n+1)/2];
    int index = 1;
    int counter = 2;
    for(int i = 0;i<array.length;i++){
    array[i]= index++;
    if(index ==counter){
    counter++;
    index = 1;
    }
    }
    return array;
    }

    Reply
  4. Stefan

    public int[] squareUp(int n) {
    int index = 1;
    int counter = 0;
    int array[] = new int[n*n];
    for(int i = array.length-1;i>=0;i–){
    if(index<=n-counter)
    array[i]=index++;
    if(i%n==0){
    counter++;
    index = 1;
    }
    }
    return array;
    }

    Reply
  5. Ekso

    Hello! I was wondering if you could display a more efficient solution to maxMirror (without reversing input). I read your note and wondered out of curiosity what you would have done if comprehensibility wasn’t an issue.

    Reply
    1. Gregor Ulm Post author

      Why would I want to obfuscate my code for the sake of an imagined performance increase? In terms of performance, the difference between filling an array from the front vs from the back is either negligible or zero (look up ‘branch prediction’), and would depend on implementation details of the JVM. I would guess that there is no noticeable difference in performance. At least I have no problems coming up with effectively identical JVM byte code for both cases. If you really were concerned with performance optimisation at this level, you should ask yourself why you would want to write your program in Java in the first place, though.

      Reply
  6. Raunak Pillai

    int [] arr = new int[n*n];
    int i = 1;
    while(i 0){
    if(temp <= i){
    arr[index++] = temp;
    }
    else{
    arr[index++] = 0;
    }
    temp–;
    }
    i++;
    }

    Reply
  7. Alex

    maxMirror is massive… maybe try this:

    public int maxMirror(int[] nums) {
    int max = 0;
    for(int i = 0; i = 0 && start < nums.length){
    if(nums[start] == nums[end]){
    count++;
    max = Math.max(max, count);
    start++;
    }else{
    count = 0;
    start = i;
    }
    end–;
    }
    }
    return max;
    }

    Reply
    1. Alex

      Formatter is messing up the code…?

      public int maxMirror(int[] nums) {
      int max = 0;
      for(int i = 0; i = 0 && start < nums.length){
      if(nums[start] == nums[end]){
      count++;
      max = Math.max(max, count);
      start++;
      }else{
      count = 0;
      start = i;
      }
      end–;
      }
      }
      return max;
      }

      Reply
  8. ArchyBald


    public int maxMirror(int[] nums) {

     int max = 0;

     int numsLength = nums.length;

     for (int start = 0; start < numsLength; start++) {

      if (start + max > numsLength - 1) {

       break;

      }

      int count = 0;

      for (int end = numsLength - 1; end >= 0; end--) {

       if (count + start < numsLength) {

        if (nums[start + count] == nums[end]) {

         count++;

         max = Math.max(max, count);

        } else if (count > 0) {

         count = 0;

         end++;

        }

       }

      }

     }

     return max;

    }

    Reply
  9. ArchyBald


    public int maxMirror(int[] nums) {
    int max = 0;
    int numsLength = nums.length;
    for (int start = 0; start numsLength - 1) {
    break;
    }
    int count = 0;
    for (int end = numsLength - 1; end >= 0; end--) {
    if (count + start 0) {
    count = 0;
    end++;
    }
    }
    }
    }
    return max;
    }

    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.