Leet Code Problems & Solutions:

Problem Statement

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example

Input: [1,2,3,1]
Output: true

Brute Force Solution

Lets talk about the simplest solution first.

You can have two loops
Outer loop iterate over complete array
Inner loop covers rest of the array
Just check if rest of the array contains same number or not

Code

public boolean containsDuplicate_bruteforce(int[] nums) {
   if (nums == null || nums.length == 0) return false;
   
   int l = nums.length;
   for (int i=0; i<l; i++) {
      for (int j=i+1; j<l; j++) {
         if (nums[i] == nums[j]) {
            return true;
         }
      }
   }
   return false;
}

Complexity

Its O(n^2)

Another Solution - Sorting

Another simple solution is to sort the numbers first. Then, match consecutive numbers. If you find any pair having same value, return true.

Code

public boolean containsDuplicate(int[] nums) {
   if (nums == null || nums.length == 0) return false;
   
   Arrays.sort(nums);
   int l = nums.length;
   for (int i=1; i<l; i++) {
      if (nums[i-1] == nums[i]) {
         return true;
      }
   }
   return false;
}

Complexity

Complexity for sorting is O(nlogn) Total complexity is also O(nlogn)

Another Solution using Extra Memory - HashSet

Lets utilize a HashSet. A HashSet is a data structure which contains all unique elements, and the complexity to search and adding an element is O(1)

public boolean containsDuplicate_extraMemory(int[] nums) {
   if (nums == null || nums.length == 0) return false;
   
   Set<Integer> set = new HashSet<>();
   int l = nums.length;
   for (int i=0; i<l; i++) {
      if (set.contains(nums[i])) {
         return true;
      }
      set.add(nums[i]);
   }
   return false;
}

Complexity

Its O(n)

===========================================================================

2)//Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator in O(n) time.

//Example :

//Input: arr[] = {10, 3, 5, 6, 2}

//Output: prod[] = {180, 600, 360, 300, 900}

//3 * 5 * 6 * 2 product of other array

//elements except 10 is 180

//10 * 5 * 6 * 2 product of other array

//elements except 3 is 600

//10 * 3 * 6 * 2 product of other array

//elements except 5 is 360

//10 * 3 * 5 * 2 product of other array

//elements except 6 is 300

//10 * 3 * 6 * 5 product of other array

//elements except 2 is 900

===============

public class MyClass {

public static void main(String args[]) {

int[] num={1,2,3,4};

productArray(num,4);

}

private static void productArray(int[] arr,int n){

//base case

if(n==1){

System.out.println(0);

return;

}

//initialize the array - left, right & prod

int[] left=new int[n];

int[] right=new int[n];

int[] prod=new int[n];

//initilize the variables

int i,j;

// Left most element of the left array is 1

left[0]=1;

//right most element of the right array is 1

right[n-1]=1;

//construct the left array

for(i=1;i<n;i++){

left[i]=arr[i-1]*left[i-1];

}

//construct the right array

for(j=n-2;j>=0;j--){

right[j]=arr[j+1]*right[j+1];

}

//construct the prod array

for(i=0;i<n;i++){

prod[i]=left[i]*right[i];

}

//print the prod array

for(i=0;i<n;i++){

System.out.print(prod[i]+"\t");

}

========================================================================

LeetCode – Maximum Subarray (Java)

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Java Solution - DP

The easiest way to formulate the solution of this problem is using DP. Let f(n) be the maximum subarray for an array with n elements. We need to find the subproblem and the relation.

The changing condition for dynamic programming is "We should ignore the sum of the previous n-1 elements if nth element is greater than the sum."

public int maxSubArray(int[] nums) {
    int result = nums[0];
    int[] sum =  new int[nums.length];
    sum[0] = nums[0];
 
    for(int i=1; i<nums.length; i++){
        sum[i] = Math.max(nums[i], sum[i-1] + nums[i]);
        result = Math.max(result, sum[i]);
    }
 
    return result;
}

The time complexity and space complexity are the same O(n). However, we can improve the space complexity and make it to be O(1).

public int maxSubArray(int[] nums) {
    int result = nums[0];
    int sum = nums[0];
 
    for(int i=1; i<nums.length; i++){
        sum = Math.max(nums[i], sum + nums[i]);
        result = Math.max(result, sum);
    }
 
    return result;
}

===============================================================

Program to remove vowels from a String

Given a string, remove the vowels from the string and print the string without vowels.

Examples:

Input : welcome to testing
Output : wlcm t tstng

Input : what is your name ?
Output : wht s yr nm ?

import java.util.Scanner;

public class Practice {

    public static void main(String[] args)

{

        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();

        for (int i = 0; i < s.length(); i++) {

            if (s.charAt(i) == 'a' || s.charAt(i) == 'e'

                || s.charAt(i) == 'i' || s.charAt(i) == 'o'

                || s.charAt(i) == 'u' || s.charAt(i) == 'A'

                || s.charAt(i) == 'E' || s.charAt(i) == 'I'

                || s.charAt(i) == 'O'

                || s.charAt(i) == 'U') {

                continue;

}

            else {

                System.out.print(s.charAt(i));

}

}

}

}

------------------------------------------------------------------------------------

// Java program to remove vowels from a String
import java.util.Arrays;
import java.util.List;
 
class GFG
{   
    static String remVowel(String str)
    {
         return str.replaceAll("[aeiouAEIOU]", "");
    }
     
    // Driver Code
    public static void main(String[] args)
    {
        String str = "A Computer Science Portal for Testers";       
        System.out.println(remVowel(str));
    }
}

replaceAll(String regex, String replacement) is a method of String objects that replaces any parts of the string that matches the provided regular expression (regex) with a replacement. In regex, "[ ]" matches characters that in the bracket; e.g. "[abc]" matches any "a", "b", or "c". "[^ ]" matches characters not in the bracket; e.g. "[^ab]" will match "c" in String "abc". String J was concatenated to "[^" and "]" to create the regex "[^ (all characters in J) ]" in order to replace any characters of S that is not in J with a blank "".
===================================================

Defanged Version of Internet Protocol Address

Difficulty Level : Basic
Last Updated : 02 Feb, 2022

Read

Discuss

Given a valid (IPv4) Internet Protocol address S, the task is to find the defanged version of that IP address.
Defanged Version of IP Address: is in which every period “.” is replaced by “[.]”. 
Examples: 
 
Input: S = “1.1.1.1” 
Output: 1[.]1[.]1[.]1
Input: S = “255.100.50.0” 
Output: 255[.]100[.]50[.]0 
// Java implementation to find the
// defanged version of the IP address
class DefangedVersionIPAddress{
// Function to generate a defanged 
// version of IP address.
static String generateDefangIP(String str)
{
    String defangIP = "";
     
    // Loop to iterate over the
    // characters of the string
    for(int i = 0; i < str.length(); i++)
    {
       char c = str.charAt(i);
       if(c == '.')
       {
           defangIP += "[.]";
       }
       else
       {
           defangIP += c;
       }
    }
    return defangIP;
}
 
// Driver Code
public static void main(String[] args)
{
    String str = "255.100.50.0";
     
    System.out.println(generateDefangIP(str));
}
} 

==========================================================================

LeetCode #5 - Longest Palindromic Substring

October 18, 2020

Hello LeetCode enthusiasts 👋! It’s a brand new day and it’s time for solving a new LeetCode problem - Longest Palindromic Substring.
0005 - Longest Palindromic Substring.
Problem StatementGiven a string s, return the longest palindromic substring in s.
Constraints1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case).
ExamplesExample 1:
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Example 3:
Input: s = "a"
Output: "a"
Example 4:
Input: s = "ac"
Output: "a"
AnalysisThis problem is pretty simple. We are given a string and we have to find a substring which is the longest palindrome.
A palindrome is the one which is equal if read from left to right and from right to left.
For e.g., in the string abbaa, palindromes are - abba, bb, aa. Our output should be abba as it is the longest.
ApproachThere are many ways to solve this problem. Most common way is to treat each character of the string as the center and expand left and right. Keep track of their lengths and return the string with maximum length.
So, what’s the problem 🤔? The problem is the time complexity - it will be O(n2). Not so good, right?
Let’s see what’s hurting us. We are expanding left and right treating each character as the center. What if we only expand only at the necessary characters instead of expanding at each character?
Can we do that 🤔? Yes, we can using the Manacher’s Algorithm. This algorithm intelligently uses characteristics of a palindrome to solve the problem in linear O(n) time -
The left side of a palindrome is a mirror image of its right side.
Odd length palindrome will be centered on a letter and even length palindrome will be centered in between the two letters (thus there will be total 2n + 1 centers).
Manacher’s Algorithm deals with the problem of finding the new center. Below are the steps -
Initialize the lengths array to the number of possible centers.
Set the current center to the first center.
Loop while the current center is valid:
(a) Expand to the left and right simultaneously until we find the largest palindrome around this center.
(b) Fill in the appropriate entry in the longest palindrome lengths array.
(c) Iterate through the longest palindrome lengths array backwards and fill in the corresponding values to the right of the entry for the current center until an unknown value (as described above) is encountered.
(d) set the new center to the index of this unknown value.
Return the longest substring.
Time ComplexityNote that at each step of the algorithm we’re either incrementing our current position in the input string or filling in an entry in the lengths array. Since the lengths array has size linear in the size of the input array, the algorithm has worst-case linear O(n) running time.
Space ComplexitySince we are using the palindrome array to store the length of palindromes centered at each character, the space complexity will also be O(n).
CodeJavapublic class LongestPalindromicSubstring {

    public String longestPalindrome(String s) {
        // Update the string to put hash "#" at the beginning, end and in between each character
        String updatedString = getUpdatedString(s);
        // Length of the array that will store the window of palindromic substring
        int length = 2 * s.length() + 1;
        // Array to store the length of each palindrome centered at each element
        int[] p = new int[length];
        // Current center of the longest palindromic string
        int c = 0;
        // Right boundary of the longest palindromic string
        int r = 0;
        // Maximum length of the substring
        int maxLength = 0;
        // Position index
        int position = -1;
        for (int i = 0; i < length; i++) {
            // Mirror of the current index
            int mirror = 2 * c - i;
            // Check if the mirror is outside the left boundary of current longest palindrome
            if (i < r) {
                p[i] = Math.min(r - i, p[mirror]);
            }
            // Indices of the characters to be compared
            int a = i + (1 + p[i]);
            int b = i - (1 + p[i]);
            // Expand the window
            while (a < length && b >= 0 && updatedString.charAt(a) == updatedString.charAt(b)) {
                p[i]++;
                a++;
                b--;
            }
            // If the expanded palindrome is expanding beyond the right boundary of
            // the current longest palindrome, then update c and r
            if (i + p[i] > r) {
                c = i;
                r = i + p[i];
            }
            if (maxLength < p[i]) {
                maxLength = p[i];
                position = i;
            }
        }
        int offset = p[position];
        StringBuilder result = new StringBuilder();
        for (int i = position - offset + 1; i <= position + offset - 1; i++) {
            if (updatedString.charAt(i) != '#') {
                result.append(updatedString.charAt(i));
            }
        }
        return result.toString();
    }

    private String getUpdatedString(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            sb.append("#").append(s.charAt(i));
        }
        sb.append("#");
        return sb.toString();
    }
}

LeetCode #20 - Valid Parentheses

November 15, 2020

Hello fellow devs 👋! It’s a brand-new day and it’s time to solve another problem from LeetCode.
Valid Parentheses
Problem StatementGiven a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Constraints1 ≤ s.length ≤ 104
s consists of parentheses only '()[]{}'.
ExamplesExample 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([)]"
Output: false
Example 5:
Input: s = "{[]}"
Output: true
AnalysisIn this question, we need to deal with only 6 symbols — (, ), {, }, [, ]. We will be given a string containing only these symbols. A string is valid if all the symbols are present in pairs and left parenthesis comes before the corresponding right.
ApproachThis is a simple question 😃. We will traverse the string s from left to right and see if left and right parentheses are matching with their corresponding counterpart.
Traverse the string from left to right.
If we encounter the open/left parenthesis, then we will push it to the Stack data structure due to its Last In First Out (LIFO) property.
If we encounter any of the close/right parentheses, we will check it with the top of the stack. If it is the correct corresponding open/left parenthesis, we will move further, else we will return false.
At last, for valid string, the stack should be empty because all the left parentheses should have matched with the right ones.
Time ComplexityWe are traversing the string once, hence the time complexity will be O(n).
Space ComplexityWe are using Stack to store characters of the string, hence the space complexity will be O(n).
CodeJavapublic class ValidParentheses {

    public boolean isValid(String s) {
        // Stack to store left symbols
        Stack<Character> leftSymbols = new Stack<>();
        // Loop for each character of the string
        for (char c : s.toCharArray()) {
            // If left symbol is encountered
            if (c == '(' || c == '{' || c == '[') {
                leftSymbols.push(c);
            }
            // If right symbol is encountered
            else if (c == ')' && !leftSymbols.isEmpty() && leftSymbols.peek() == '(') {
                leftSymbols.pop();
            } else if (c == '}' && !leftSymbols.isEmpty() && leftSymbols.peek() == '{') {
                leftSymbols.pop();
            } else if (c == ']' && !leftSymbols.isEmpty() && leftSymbols.peek() == '[') {
                leftSymbols.pop();
            }
            // If none of the valid symbols is encountered
            else {
                return false;
            }
        }
        return leftSymbols.isEmpty();
    }
}

LeetCode #34 - Find First And Last Position Of Element In Sorted Array

March 12, 2021

Hello LeetCode enthusiasts 👋! Today we will be discussing a new problem which uses variation of binary search.
Find First And Last Position Of Element In Sorted Array
Problem StatementGiven an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
Constraints:0 ≤ nums.length ≤ 105
-109 ≤ nums[i] ≤ 109
nums is a non-decreasing array.
-109 ≤ target ≤ 109
Follow upCould you write an algorithm with O(log n) runtime complexity?
ExamplesExample 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
AnalysisWe have a sorted array nums and a target value which we need to search in the array. This description suggests that it is a clear case of binary search. The catch is that the target can be repeated in the array.
Thus, there might be multiple indices where the target can be found. Thus, we need to find these indices. If the element is not found then we should return -1.
ApproachWe will use binary search algorithm to find the first and last occurrences of the target separately.
For first occurrence, we will first find the index of the number and then search again in the left subarray as long as we are finding the number.
For last occurrence, we will first find the index of the number and then search again in the right subarray as long as we are finding the number.
Time ComplexitySince we are using binary search which halves the number of elements to be considered after each step, therefore, the time complexity will be O(log n).
Space ComplexityWe are not using any data structures for the intermediate calculations, hence the space complexity will be O(1).
CodeJavapublic class FindFirstAndLastPositionOfElementInSortedArray {

    public int[] searchRange(int[] nums, int target) {
        return new int[]{findFirstOccurrence(nums, target), findLastOccurrence(nums, target)};
    }

    private int findFirstOccurrence(int[] nums, int target) {
        // Left and right pointers
        int left = 0;
        int right = nums.length - 1;
        // Index of first occurrence
        int firstOccurrence = -1;
        // Loop until the two pointers meet
        while (left <= right) {
            // Middle index
            int middle = left + (right - left) / 2;
            // Check if we have found the value
            if (nums[middle] == target) {
                firstOccurrence = middle;
                right = middle - 1;
            }
            // If the target is less than the element
            // at the middle index
            else if (target < nums[middle]) {
                right = middle - 1;
            }
            // If the target is greater than the element
            // at the middle index
            else {
                left = middle + 1;
            }
        }
        return firstOccurrence;
    }

    private int findLastOccurrence(int[] nums, int target) {
        // Left and right pointers
        int left = 0;
        int right = nums.length - 1;
        // Index of first occurrence
        int lastOccurrence = -1;
        // Loop until the two pointers meet
        while (left <= right) {
            // Middle index
            int middle = left + (right - left) / 2;
            // Check if we have found the value
            if (nums[middle] == target) {
                lastOccurrence = middle;
                left = middle + 1;
            }
            // If the target is less than the element
            // at the middle index
            else if (target < nums[middle]) {
                right = middle - 1;
            }
            // If the target is greater than the element
            // at the middle index
            else {
                left = middle + 1;
            }
        }
        return lastOccurrence;
    }
}

Source:https://redquark.org/

Automation QA Testing Course Content