Category: Arrays

Find Numbers with Even Number of Digits

August 14th, 2020

Given an array nums of integers, return how many of them contain an even number of digits.

Example 1:

Input: nums = [12,345,2,6,7896]
Output: 2

Example 2:

Input: nums = [555,901,482,1771]
Output: 1

Solution

Loop through Array
Find number of digits in each number
Increase counter by 1 if number of digits in the number is even

/**
 * FindNumbersWithEvenNumberOfDigits.java
 * Purpose: Find Numbers with Even Number of Digits
 *
 * @author Megha Rastogi
 * @version 1.0 08/09/2020
 */
class FindNumbersWithEvenNumberOfDigits {

    /**
     * Find Numbers with Even Number of Digits
     *
     * @param Array, nums
     * @return integer, numberOfEvenDigitNumbers
     */
    public int findNumbers(int[] nums) {
        
        // initialize the variable to store the count of
        // even digit numbers
        int numberOfEvenDigitNumbers = 0;
        
        // loop through the array and increase the counter
        // if number of digits are even
        for(int num: nums){
            if(numberOfDigits(num) % 2 == 0)
                numberOfEvenDigitNumbers++;
        }
        
        //return the result
        return numberOfEvenDigitNumbers;
    }
    
    /**
     * Find number of digits in an integer
     *
     * @param integer, num
     * @return integer, numberOfDigits
     */
    public int numberOfDigits(int num){
        
        // initialize the counter to store number of digits
        int numberOfDigits = 0;
        
        // loop until number is greater than 0
        // Continuously divide num by 10
        // increase the numberOfDigits by 1
        while(num > 0){
            num /= 10;
            numberOfDigits++;
        }
        
        // return  the result
        return numberOfDigits;
    }
}

Source – Leetcode

Code – FindNumbersWithEvenNumberOfDigits.java

Squares of a Sorted Array

August 9th, 2020

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

Solution

The straightforward solution that comes to mind after reading the problem statement is –

Loop through the array and replace each number by its square.
Sort the resulting array.

The space complexity of O(1) as we are using the same array and no extra space. But the time complexity is O(n log n) ie the complexity of sorting.

/**
 * SquareSortedArray.java
 * Purpose: Squares of a Sorted Array
 *
 * @author Megha Rastogi
 * @version 1.0 08/09/2020
 */
class SquareSortedArray {
   /**
     * Find Squares of a Sorted Array
     *
     * @param Array, A
     * @return Array, A
     */
    public int[] sortedSquares(int[] A) {
    
        // loop through the array and replace each element
        // by it's square
        for(int i = 0; i < A.length; i++){
            A[i] = A[i] * A[i];
        }
        
        // Sort the squared array
        Arrays.sort(A);
        
        // return the sorted array
        return A;
    }
}

Optimized Solution

Another solution is using the two pointer technique. Since array is sorted and it has negative and positive elements, the squares of negative will be in decreasing order and that of positive will be in increasing order. We can use this information and compare the start element with end element and put the larger element at the end position.

Initialize two pointers start and end pointing to start and end indices of the array. Also initialize another pointer (index) to keep track of current index of result array.
Loop until start <= end
1. Find the square of the start (powStart) and end (powEnd) elements.
2. If powStart > powEnd, result[index] becomes powStart, increment index, increment start.
3. if powEnd > powStart, result[index] becomes powEnd, increment index, decrement end.

Here the time complexity becomes O(n) and space complexity is also O(n)

/**
 * SquareSortedArrayOptimized.java
 * Purpose: Squares of a Sorted Array
 *
 * @author Megha Rastogi
 * @version 1.0 08/09/2020
 */
class SquareSortedArrayOptimized {
   /**
     * Find Squares of a Sorted Array
     *
     * @param Array, A
     * @return Array, ans
     */
    public int[] sortedSquares(int[] A) {
    
        // return null if array is null
        if (A == null) return null;
        
        // initialize the result array
        int [] ans = new int[A.length];
     
        // initialize start and end pointers to start and end index of array
        int start = 0, end = A.length - 1;
       
        int i = end; // insert position.
       
        // Loop until start is less than equal to end
        while (start <= end) { 
            
            // finding square of start and end element
            int pow1 = A[start] * A[start];
            int pow2 = A[end] * A[end];
           
            // if power of start is bigger, 
            // ith element must be start element
            // increment start as we placed first negative number
            // else ith element will be end element
            if (pow1 > pow2) {
                ans[i--] = pow1;
                start++;
            } else {
                ans[i--] = pow2;
                end--;
            }
        }
       
        // return the result array
        return ans;
    }
}

Source – leetcode

Code – SquareSortedArray.java, SquareSortedArrayOptimized.java

Move Zeros To End

July 31st, 2020
Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Example:
```
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
```
Note:
1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.
Solution

One of the solutions is to create new array of the same size as input array. Add the non zero values to the new array. Add zero to the remaining positions at the last. The time complexity is linear, but the space complexity is O(n), n being the size of array.

But we can do this without using that extra array. We keep track of index. And iterate over the array, updating the index position with the current element if current element is not zero. Then looping to make all elements from index to last zero. This will make the space complexity O(1).
```
/**
 * MoveZerosToEnd.java
 * Purpose: Move zeros to end.
 *
 * @author Megha Rastogi
 * @version 1.0 07/13/2020
 */
class MoveZerosToEnd {

    /**
     * Move zeros to end of array
     *
     * @param Array, nums
     */
    public void moveZeroes(int[] nums) {
        
        // track index to keep track of non zero elements
        int index = 0;
        
        // Loop through the array and 
        // if element is not zero make it the
        // indexth element
 		    for(int arr_i = 0; arr_i < nums.length; arr_i++) {
 			    if(nums[arr_i] != 0){
 				    nums[index++] = nums[arr_i];
          }
        }
        
        // Loop from index to end to make the end elements zero
 		    for(int arr_i = index; arr_i < nums.length; arr_i++){
 			    nums[arr_i] = 0;
        }
    }
}
```
Source – leetcode

Code – MoveZerosToEnd.java
Single Number

July 17th, 2020
Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1
```
Input: [2,2,1]
Output: 1
```
Example 2
```
Input: [4,1,2,1,2]
Output: 4
```
Solution

A simple approach using extra space is to use a HashMap of the integers as keys and counts as value. Then iterate over the HashMap to find the key with value 1. That will give us a time complexity of O(n) and space complexity of O(n), n being the size of the array.

Another more simple approach is to use XOR (bit manipulation). Given two numbers, a and b, as we know an XOR a is 0 and 0 ^ b is b. So we can iterate over the array and keep XORing the elements with one another, similar ones will cancel out and we will get the unique one.
```
/**
 * SingleNumber.java
 * Purpose: Find maximum sum contiguous subarray 
 *
 * @author Megha Rastogi
 * @version 1.0 07/13/2020
 */
class SingleNumber {

    /**
     * Find unique number in an array of duplicates 
     *
     * @param Array, nums
     * @return integer, ans
     */
    public int singleNumber(int[] nums) {
       
        int ans = 0;
        
        // looping through the array and using XOR
        // as a ^ a is 0 and 0 ^ b is b
        for(int i = 0; i < nums.length; i++){
            ans ^= nums[i];
        }
        return ans;
    }
}
```
Source – leetcode

Code – SingleNumber .java
Maximum Subarray

June 6th, 2020
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:
```
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```
Solution

We need to find the maximum sum contiguous subarray here. Let’s start from the example above. Let’s keep track of sum and maxSum which is a very small number N. And start summing from the beginning –
- for -2, sum is -2, maxSum will still become -2.
- sum of -2 and 1 will be -1, A thing to note here is our new sum -1 is less than the current value 1. So our sum should become 1 and max between -2 and 1 is 1. Therefore our maxSum is also 1.
- sum of 1 and -3 is -2. maxSum between -2, 1 is 1.
- sum of -2 and 4 is 2, which is less than 4. so sum becomes 4. and maxSum becomes 4.
- And we keep doing this until we reach end.
Our basic algorithm will be
- Take two variables sum and maxSum to keep track of sum and maxSum till a given position in array.
- Loop through the array
  - sum is addition of sum and current value in the array. If sum < current value in the array, sum becomes current value in the array.
  - maxSum is maximum of maxSum and sum.
  - Repeat above steps until we reach the end of the loop.
- return the maxSum
```
/**
 * MaxSubArray.java
 * Purpose: Find maximum sum contiguous subarray 
 *
 * @author Megha Rastogi
 * @version 1.0 06/06/2020
 */
class MaxSubArray {
    
    /**
     * Find maximum sum contiguous subarray 
     *
     * @param Array, nums
     * @return integer, maxSum
     */
    public int maxSubArray(int[] nums) {
        
        // Initalize maxSum and sum
        int maxSum = Integer.MIN_VALUE, sum = 0;
        
        // Loop through the array
        for(int i = 0; i < nums.length; i++){
            
            // add current value to sum
            sum+=nums[i];
            
            // update sum if it becomes less than current value
            if(sum < nums[i])
                sum = nums[i];
            
            // update the max sum
            maxSum = Math.max(maxSum, sum);
        }
        
        //return the max sum
        return maxSum;
    }
}
```
Code – MaxSubArray.java

Source – Leetcode
Last Stone Weight

April 17th, 2020
We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
- If x == y, both stones are totally destroyed;
- If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

Example 1
```
Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.
```
Note:
1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 1000
Solution

The problem statement itself states that at each iteration we need to pick out the max two elements. So we need some sort of sorting to always get the max two elements.

We can use the heap data structure to maintain a sorted state of elements and always pick out the max two. The algorithm would be like this.
1. Add all the elements of the array to the max heap.
2. Loop until heap size is greater than equal to two
  1. Take out the max two elements x, y;
  2. if they are not equal, insert x – y back into the heap.
3. return 0 if the heap is empty, else return the top element of the heap.
The time complexity is O(n log n) and space complexity is O(n) where n is the size of the array.
```
class Solution {
    public int lastStoneWeight(int[] stones) {
        
        //Initialize Priority Queue to Max Heap
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        
        //add all elements of stones array to priority queue
        for(int stone: stones){
            pq.add(stone);
        }
        
        //Loop until the heap has atleast two elements.
        while(pq.size() >= 2){
            
            //Pop out the two max elements
            int x = pq.poll();
            int y = pq.poll();
            
            //Push the difference between the two values back into the queue
            if(x != y){
                pq.add(x - y);
            }
        }
        
        // return 0 is queue is empty, else the top element
        return pq.isEmpty() ? 0 : pq.poll();
    }
}
```
Source – LeetCode

Code – LastStoneWeight.java

Category: Arrays

Find Numbers with Even Number of Digits

Solution

Squares of a Sorted Array

Solution

Optimized Solution

Move Zeros To End

Solution

Single Number

Solution

Maximum Subarray

Solution

Last Stone Weight

Example 1

Solution