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); }

Joseph BleauHi 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

Joseph BleauWell, 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

JeffI 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;

}

Daren ZouI 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;

}

LeiWe 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;

}

Gregor UlmPost authorLei,

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.

WOJTEKHi Lei

I think Your solution is truly working for fix34. Gregor big thanks for Your hard work but Your solution to fix34 is not complete.

Patryk DziedzicHello

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;

}

S SinghHi,

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;

}

Gregor UlmPost authorThanks 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.

aureusUp, 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.

JeremyA 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;

}

JeremyI 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;

}

Stefanpublic 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;

}

Stefanpublic 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;

}

Stefanpublic 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;

}

Stefanpublic 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;

}

AmbarishHi Stefan,

Your code doesn’t work for {1, 2, 1, 2, 3}. The answer is 3. But your code is returning 4.

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

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