Tag: leetcode solutions

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

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

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