Lets Code Them Up!

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

Diameter of the Binary Tree

August 7th, 2020

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of the path between two nodes is represented by the number of edges between them.

Solution

It’s clear that we need to find the length of the longest path between two nodes in a tree. So here those nodes are either 4 and 3 or 5 and 3. Both 5 and 5 are the leaf nodes of the right subtree and 3 is the leaf node of the left subtree. The depth of the tree is the max length from root to leaf. It could be safely said, the max diameter will be the max depth of left subtree and right subtree at any time. For a node root of the tree, we need to do following –

Find the depth of left child
Find the depth of right child
Update global variable diameter with the sum of left and right depth if it is more than depth’s current value.
return depth of the root

Both the time and space complexity will of O(n) where n is the number of nodes in the binary tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
/**
 * DiameterOfBinaryTree.java
 * Purpose: Find the diameter of Binary Tree
 *
 * @author Megha Rastogi
 * @version 1.0 08/03/2020
 */
class DiameterOfBinaryTree {
    // ans variable to track diameter
    int ans = 0;
    
    /**
     * Find the diameter of Binary Tree
     *
     * @param root, TreeNode
     * @return integer, diameter
     */
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null)
            return 0;
        depth(root);
        return ans-1;
    }
    
    /**
     * Helper method to find the diameter of a binary tree
     *
     * @param root, TreeNode
     * @return integer, diameter
     */
    public int depth(TreeNode root){
        // return 0 when reaching leaf nodes
        if(root == null)
            return 0;
        
        // left node depth
        int left = depth(root.left);
     
        // right node depth
        int right = depth(root.right);
     
        // update diameter with the max diameter till now
        ans = Math.max(ans, left+right+1);
     
        //return depth till this node
        return Math.max(left, right)+1;
    }
}

Source – leetcode

Code – DiameterOfBinaryTree.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

Happy Number

July 24th, 2020

Write an algorithm to determine if a number n is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example:

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Solution

From the problem statement it is clear –

Find the sum of the digits of the number.
If sum is one, return true, we found our happy number.
Keep adding to some list/set if it’s already not there.
If sum is already in a list/set, return false.
If none of the above conditions are met, keep repeating above steps for every new sum.

The time complexity of this solution is O(log n) where n is the input number. Space complexity is O(log n) where n is the input number.

/**
 * HappyNumber.java
 * Purpose: Determine if a number is happy
 *
 * @author Megha Rastogi
 * @version 1.0 07/13/2020
 */
class HappyNumber {

    // Set to track the sum of squares encountered till now
    HashSet<Integer> cache = new HashSet<Integer>();
    
    /**
     * Determine if a number is happy
     *
     * @param integer, n
     * @return boolean, ans
     */
    public boolean isHappy(int n) {
    
        // find sum of squares of digits
        int sum = findSum(n);
        
        // if sum is 1, we found a happy number
        // return true
        if(sum == 1)
            return true;
            
        // if sum is already present in the cache
        // number is not happy, return false
        if(cache.contains(sum))
            return false;
            
        // add sum to cache
        cache.add(sum);
        
        // Find if the new number is happy or not
        return isHappy(sum);
    }
    
    /**
     * Determine sum of squares of each
     * digit in number
     *
     * @param integer, n
     * @return integer, sum
     */
    public int findSum(int n){
        
        // variable to keep track of sum
        int sum = 0;
        
        // Find each digit of the number and
        // add square of that digit to sum
        while(n > 0){
        
            // determine remainder, last digit
            int rem = n % 10;
            
            // add sqaure of remainder to sum
            sum += (rem * rem);
            
            // divide number by 10 to loose the last digit
            n = n/10;
        }
        
        // return sum of squares of each digit
        return sum;
    }
}

Source – leetcode

Code – HappyNumber.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

Squares of a Sorted Array

Solution

Optimized Solution

Diameter of the Binary Tree

Solution

Move Zeros To End

Solution

Happy Number

Solution

Single Number

Solution

Maximum Subarray

Solution