Array-3

Ref

• https://dev-wannabe.pl/codingbat/

• https://github.com/mirandaio/codingbat

/* Given a non-empty array, return true if there is a place to split the 
 * array so that the sum of the numbers on one side is equal to the sum of 
 * the numbers on the other side.
 */
public boolean canBalance(int[] nums) {
    int first = 0;
    int second = 0;
      
    for(int i = 0; i < nums.length; i++)
        second += nums[i];
              
    for(int i = 0; i <= nums.length - 2; i++) {
        first += nums[i];
        second -= nums[i];
                            
        if(first == second)
            return true;
    }
                                          
    return false;
}

/* Say that a "clump" in an array is a series of 2 or more adjacent elements 
 * of the same value. Return the number of clumps in the given array.
 */
public int countClumps(int[] nums) {
    int count = 0;
    int i = 0;
      
    while(i < nums.length) {
        int val = nums[i];
        i++;
        int length = 1;
        while(i < nums.length && nums[i] == val) {
            i++;
            length++;
        }
                                            
        if(length > 1)
            count++;
    }
                                                          
    return count;
}

/* Return an array that contains exactly the same numbers as the given array, 
 * but rearranged so that every 3 is immediately followed by a 4. Do not move 
 * the 3's, but every other number may move. 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.
 */
public int[] fix34(int[] nums) {
    int i = 0;
    
    while(i < nums.length && nums[i] != 3)
        i++;
              
    int j = i + 1;
                  
    while(j < nums.length && nums[j] != 4)
        j++;
                            
    while(i < nums.length) {
        if(nums[i] == 3) {
            int temp = nums[i+1];
            nums[i+1] = nums[j];
            nums[j] = temp;
                                                          
            while(j < nums.length && nums[j] != 4)
                j++;
        }
        i++;
    }

    return nums;
}

/* Return an array that contains exactly the same numbers as the given array, 
 * but rearranged so that every 4 is immediately followed by a 5. Do not move 
 * the 4's, but every other number may move. The array contains the same 
 * number of 4's and 5's, and every 4 has a number after it that is not a 4. 
 * In this version, 5's may appear anywhere in the original array.
 */
public int[] fix45(int[] nums) {
    int i = 0;
    int j = 0;
        
    while(j < nums.length && nums[j] != 5)
        j++;
                  
    while(i < nums.length) {
        if(nums[i] == 4) {
            int temp = nums[i+1];
            nums[i+1] = nums[j];
            nums[j] = temp;
                                                
            while((j < nums.length && nums[j] != 5) || j == i + 1)
                j++;
        }
        i++;
    }
                                                                          
    return nums;
}

/* Given two arrays of ints sorted in increasing order, outer and inner, 
 * return true if all of the numbers in inner appear in outer. The best 
 * solution makes only a single "linear" pass of both arrays, taking 
 * advantage of the fact that both arrays are already in sorted order.
 */
public boolean linearIn(int[] outer, int[] inner) {
    int i = 0;
    int j = 0;
      
    while(i < inner.length && j < outer.length) {
        if(inner[i] > outer[j]) {
            j++;
        } else if(inner[i] < outer[j]) {
            return false;
        } else {
            i++;
        }
    }
                                              
    if(i != inner.length)
        return false;
                                                      
    return true;
}

/* We'll say that a "mirror" section in an array is a group of contiguous 
 * elements such that somewhere in the array, the same group appears in 
 * reverse order. For example, the largest mirror section in 
 * {1, 2, 3, 8, 9, 3, 2, 1} is length 3 (the {1, 2, 3} part). Return the size 
 * of the largest mirror section found in the given array.
 */
public int maxMirror(int[] nums) {
    int max = 0;
    
    for(int i = 0; i < nums.length; i++) {
        int count = 0;
        for(int j = nums.length - 1; j >= 0 && i + count < nums.length; j--) {
            if(nums[i + count] == nums[j]) {
                count++;
            } else {
                max = Math.max(max, count);
                count = 0;
            }
        }
                                                                
        max = Math.max(max, count);
    }

    return max;
}

/* Consider the leftmost and righmost appearances of some value in an array. 
 * We'll say that the "span" is the number of elements between the two 
 * inclusive. A single value has a span of 1. Returns the largest span found 
 * in the given array. (Efficiency is not a priority.)
 */
public int maxSpan(int[] nums) {
    int max = 0;
    
    for(int i = 0; i < nums.length; i++) {
        int j = nums.length - 1;
              
        while(nums[i] != nums[j])
            j--;
                              
        int span = j - i + 1;
                                      
        if(span > max)
            max = span;
    }
                                                    
    return max;
}

/* Given n>=0, create an array with the pattern 
 * {1,    1, 2,    1, 2, 3,   ... 1, 2, 3 .. n} (spaces added to show the 
 * grouping).
 */
public int[] seriesUp(int n) {
    int[] arr = new int[n*(n+1)/2];
    
    int index = 0;
        
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < i; j++) {
            arr[index + j] = j + 1;
        }
        index += i;
    }
                                
    return arr;
}

/* Given n>=0, create an array length n*n with the following pattern, shown 
 * here for n=3 : {0, 0, 1,    0, 2, 1,    3, 2, 1}
 */
public int[] squareUp(int n) {
    int[] arr = new int[n*n];
    
    if(n == 0)
        return arr;
              
    for(int i = n - 1; i < arr.length; i += n) {
        for(int j = i; j >= i - i / n; j--)
            arr[j] = i - j + 1;
    }
                              
    return arr;
}