For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.
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);
}
For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.
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
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
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;
}
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;
}
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;
}
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.
Hi 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.
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;
}
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;
}
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.
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.
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
Hi Stefan,
Your code doesn’t work for {1, 2, 1, 2, 3}. The answer is 3. But your code is returning 4.
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.
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.
My solution of Array-3 > linearIn is more readable .
public boolean linearIn(int[] outer, int[] inner) {
int j = 0;
for (int i = 0; i < outer.length; i++){
if (j < inner.length && outer[i] == inner[j] ) j++;
}
return j == inner.length;
}
I am not sure if you’re still interested, but I did this way in C++
long maxSpam (vector A) {
long max = 0;
long spam = 0;
vector:: iterator up;
if (A.size() == 1)
return 1;
for (int i = 0; i max)
max = spam;
}
return max;
}
I did it this way and it worked… I am too crude?
public int[] fix34(int[] nums) {
ArrayListlist=new ArrayList();
for(int x:nums)
if(x!=3 && x!=4)
list.add(x);
for(int i=0;i<nums.length;i++)
if(nums[i]==3)
{
nums[i+1]=4;
i++;
}
else
nums[i]=list.remove(0);
return nums;
}
linearIn
public boolean linearIn(int[] outer, int[] inner) {
int count = 0;
for(int num: outer){
if(count < inner.length){
if(inner[count] == num){
count++;
}
}
}
return count == inner.length;
}