Index of Topics

  1. Flow of Program
  2. First Java Program
  3. Conditionals and Loops
  4. Functions
  5. Arrays
  6. Searching
  7. Sorting
  8. Strings
  9. Patterns
  10. Recursion
  11. Bitwise Operations
  12. Math
  13. Time and Space Complexities
  14. Object-Oriented Programming (/problems/OOP)
  15. Linked List
  16. Stack and Queue
  17. Trees
  18. Heaps

Create flowchart and pseudocode for the following:

  1. Input a year and find whether it is a leap year or not.
  2. Take two numbers and print the sum of both.
  3. Take a number as input and print the multiplication table for it.
  4. Take 2 numbers as inputs and find their HCF and LCM.
  5. Keep taking numbers as inputs till the user enters ā€˜xā€™, after that print sum of all.

Write Java programs for the following:

  1. Write a program to print whether a number is even or odd, also take input from the user.
  2. Take name as input and print a greeting message for that particular name.
  3. Write a program to input principal, time, and rate (P, T, R) from the user and find Simple Interest.
  4. Take in two numbers and an operator (+, -, *, /) and calculate the value. (Use if conditions)
  5. Take 2 numbers as input and print the largest number.
  6. Input currency in rupees and output in USD.
  7. To calculate Fibonacci Series up to n numbers.
  8. To find out whether the given String is Palindrome or not.
  9. To find Armstrong Number between two given number.

Write Java programs for the following:

Basic Java Programs

  1. Area Of Circle Java Program
  2. Area Of Triangle
  3. Area Of Rectangle Program
  4. Area Of Isosceles Triangle
  5. Area Of Parallelogram
  6. Area Of Rhombus
  7. Area Of Equilateral Triangle
  8. Perimeter Of Circle
  9. Perimeter Of Equilateral Triangle
  10. Perimeter Of Parallelogram
  11. Perimeter Of Rectangle
  12. Perimeter Of Square
  13. Perimeter Of Rhombus
  14. Volume Of Cone Java Program
  15. Volume Of Prism
  16. Volume Of Cylinder
  17. Volume Of Sphere
  18. Volume Of Pyramid
  19. Curved Surface Area Of Cylinder
  20. Total Surface Area Of Cube
  21. Fibonacci Series In Java Programs
  22. Subtract the Product and Sum of Digits of an Integer
  23. Input a number and print all the factors of that number (use loops).
  24. Take integer inputs till the user enters 0 and print the sum of all numbers (HINT: while loop)
  25. Take integer inputs till the user enters 0 and print the largest number from all.
  26. Addition Of Two Numbers

Intermediate Java Programs

  1. Factorial Program In Java
  2. Calculate Electricity Bill
  3. Calculate Average Of N Numbers
  4. Calculate Discount Of Product
  5. Calculate Distance Between Two Points
  6. Calculate Commission Percentage
  7. Power In Java
  8. Calculate Depreciation of Value
  9. Calculate Batting Average
  10. Calculate CGPA Java Program
  11. Compound Interest Java Program
  12. Calculate Average Marks
  13. Sum Of N Numbers
  14. Armstrong Number In Java
  15. Find Ncr & Npr
  16. Reverse A String In Java
  17. Find if a number is palindrome or not
  18. Future Investment Value
  19. HCF Of Two Numbers Program
  20. LCM Of Two Numbers
  21. Java Program Vowel Or Consonant
  22. Perfect Number In Java
  23. Check Leap Year Or Not
  24. Sum Of A Digits Of Number
  25. Kunal is allowed to go out with his friends only on the even days of a given month. Write a program to count the number of days he can go out in the month of August.
  26. Write a program to print the sum of negative numbers, sum of positive even numbers and the sum of positive odd numbers from a list of numbers (N) entered by the user. The list terminates when the user enters a zero.

  1. Define two methods to print the maximum and the minimum number respectively among three numbers entered by the user.

  2. Define a program to find out whether a given number is even or odd.

  3. A person is eligible to vote if his/her age is greater than or equal to 18. Define a method to find out if he/she is eligible to vote.

  4. Write a program to print the sum of two numbers entered by user by defining your own method.

  5. Define a method that returns the product of two numbers entered by user.

  6. Write a program to print the circumference and area of a circle of radius entered by user by defining your own method.

  7. Define a method to find out if a number is prime or not.

  8. Write a program that will ask the user to enter his/her marks (out of 100). Define a method that will display grades according to the marks entered as below: 

 
Marks        Grade 
91-100         AA 
81-90          AB 
71-80          BB 
61-70          BC 
51-60          CD 
41-50          DD 
<=40          Fail
  1. Write a program to print the factorial of a number by defining a method named 'Factorial'. Factorial of any number n is represented by n! and is equal to 1 * 2 * 3 * .... * (n-1) *n. E.g.- 
4! = 1 * 2 * 3 * 4 = 24 
3! = 3 * 2 * 1 = 6 
2! = 2 * 1 = 2 
Also, 
1! = 1 
0! = 1

  1. Write a function to find if a number is a palindrome or not. Take number as parameter.

  2. Convert the programs in flow of program, first java, conditionals & loops assignments into functions.

  3. Write a function to check if a given triplet is a Pythagorean triplet or not. (A Pythagorean triplet is when the sum of the square of two numbers is equal to the square of the third number).

  4. Write a function that returns all prime numbers between two given numbers.

  5. Write a function that returns the sum of first n natural numbers.

Submit the following on your Leetcode profile itself.

Easy

  1. Build Array from Permutation
  2. Concatenation of Array
  3. Running Sum of 1d Array
  4. Richest Customer Wealth
  5. Shuffle the Array
  6. Kids With the Greatest Number of Candies
  7. Number of Good Pairs
  8. How Many Numbers Are Smaller Than the Current Number
  9. Create Target Array in the Given Order
  10. Check if the Sentence Is Pangram
  11. Count Items Matching a Rule
  12. Find the Highest Altitude
  13. Flipping an Image
  14. Cells with Odd Values in a Matrix
  15. Matrix Diagonal Sum
  16. Find Numbers with Even Number of Digits
  17. Transpose Matrix
  18. Add to Array-Form of Integer
  19. Maximum Population Year
  20. Determine Whether Matrix Can Be Obtained By Rotation
  21. Two Sum
  22. Find N Unique Integers Sum up to Zero
  23. Lucky Number In a Matrix
  24. Maximum Subarray
  25. Reshape the Matrix
  26. Plus One
  27. Remove Duplicates from Sorted Array
  28. Minimum Cost to Move Chips to The Same Position

Medium

  1. Spiral Matrix
  2. Spiral Matrix II
  3. Spiral Matrix III
  4. Set Matrix Zeroes
  5. Product of Array Except Self
  6. Find First and Last Position of Element in Sorted Array
  7. Jump Game
  8. Rotate Array
  9. Sort Colors
  10. House Robber

Hard

  1. Max Value of Equation
  2. First Missing Positive
  3. Good Array

Videos:

Problems:

Easy

Medium

Hard

Videos

Questions

Easy

Medium

Hard

Problems

Easy

Medium

Hard

Additionally

Pattern Questions

Print these patterns using loops:


1.  *****
    *****
    *****
    *****
    *****


2.  *
    **
    ***
    ****
    *****


3.  *****
    ****
    ***
    **
    *


4.  1
    1 2
    1 2 3
    1 2 3 4
    1 2 3 4 5


5.  *
    **
    ***
    ****
    *****
    ****
    ***
    **
    *


6.       *
        **
       ***
      ****
     *****


7.   *****
      ****
       ***
        **
         *


8.      *
       ***
      *****
     *******
    *********


9.  *********
     *******
      *****
       ***
        *


10.      *
        * *
       * * *
      * * * *
     * * * * *


11.  * * * * *
      * * * *
       * * *
        * *
         *


12.  * * * * *
      * * * *
       * * *
        * *
         *
         *
        * *
       * * *
      * * * *
     * * * * *


13.      *
        * *
       *   *
      *     *
     *********


14.  *********
      *     *
       *   *
        * *
         *


15.      *
        * *
       *   *
      *     *
     *       *
      *     *
       *   *
        * *
         *


16.           1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1


17.      1
        212
       32123
      4321234
       32123
        212
         1


18.   **********
      ****  ****
      ***    ***
      **      **
      *        *
      *        *
      **      **
      ***    ***
      ****  ****
      **********


19.    *        *
       **      **
       ***    ***
       ****  ****
       **********
       ****  ****
       ***    ***
       **      **
       *        *


20.    ****
       *  *
       *  *
       *  *
       ****

21.    1
       2  3
       4  5  6
       7  8  9  10
       11 12 13 14 15

22.    1
       0 1
       1 0 1
       0 1 0 1
       1 0 1 0 1

23.        *      *
         *   *  *   *
       *      *      *

24.    *        *
       **      **
       * *    * *
       *  *  *  *
       *   **   *
       *   **   *
       *  *  *  *
       * *    * *
       **      **
       *        *

25.       *****
         *   *
        *   *
       *   *
      *****

26.   1 1 1 1 1 1
      2 2 2 2 2
      3 3 3 3
      4 4 4
      5 5
      6

27.   1 2 3 4  17 18 19 20
        5 6 7  14 15 16
          8 9  12 13
            10 11

28.      *
        * *
       * * *
      * * * *
     * * * * *
      * * * *
       * * *
        * *
         *

29.      
       *        *
       **      **
       ***    ***
       ****  ****
       **********
       ****  ****
       ***    ***
       **      **
       *        *

30.         1
          2 1 2
        3 2 1 2 3
      4 3 2 1 2 3 4
    5 4 3 2 1 2 3 4 5


31.      4 4 4 4 4 4 4  
         4 3 3 3 3 3 4   
         4 3 2 2 2 3 4   
         4 3 2 1 2 3 4   
         4 3 2 2 2 3 4   
         4 3 3 3 3 3 4   
         4 4 4 4 4 4 4   

32.    E
       D E
       C D E
       B C D E
       A B C D E

33.    a
       B c
       D e F
       g H i J
       k L m N o
     
34.    E D C B A
       D C B A
       C B A
       B A
       A
       
35.    1      1
       12    21
       123  321
       12344321

Videos

Problems

Easy

      n = a ^ x 
      a = 2, 3, 4
      (2 ^ -31) <= n <= (2 ^ 31) - 1

Medium

Hard

Problems

Easy

Medium

Hard

Additionally

  • Click on Show problem tags and do the questions that contains tags of topics we have covered so far.

Problems

  • Click on Show problem tags and do the questions that contains tags of topics we have covered so far.

Easy

Medium

Hard

Recurrence Questions:

Akra Bazzi:

Important Topics

Interview Questions

Practice Problems

Problems

Easy

Medium

Hard

Problems

Easy

Medium

Hard

Problems

Easy

Medium

Hard

Two Sum šŸ’š

Problem Statement:

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

You may assume that each input will have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input:

nums = [2,7,11,15], target = 9

Output:

[0,1]

Explanation:
Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input:

nums = [3,2,4], target = 6

Output:

[1,2]

Example 3:

Input:

nums = [3,3], target = 6

Output:

[0,1]

Constraints:

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.

Problem Analysis:

Given that we are looking for two numbers whose sum is equal to a target, this is a classic problem that can be solved in several ways, with varying time complexities. The main goal is to find a solution with a time complexity less than O(n^2).

Approaches:

1. Brute Force Approach (O(n^2)):

A simple brute force solution would involve checking every possible pair of numbers in the array and checking if their sum equals the target.

Algorithm:

  • Loop through all pairs of elements.
  • If the sum of any pair equals the target, return the indices of the pair.

Time Complexity: O(n^2)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }
}

2. Optimized Approach with Hash Map (O(n)):

Using a hash map allows us to store numbers and their indices as we iterate through the array. This reduces the need to check every pair.

Algorithm:

  • Iterate through the array while storing each element and its index in a hash map.
  • For each element, check if target - element exists in the hash map. If so, return the indices of both elements.

Time Complexity: O(n)
Space Complexity: O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num2 = target - nums[i];
            if (map.containsKey(num2)) {
                return new int[]{map.get(num2), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

Explanation:

  • We iterate through the array once.
  • For each number, we check if the complementary number (target - nums[i]) has been seen before using the hash map. If it has, return the indices.
  • If not, we store the current number and its index in the map for future reference.

3. Optimized Approach with Two Pointers (Only works if array is sorted) (O(n)):

This approach assumes that the array is sorted. It uses two pointers to check pairs of numbers whose sum equals the target.

Algorithm:

  • Sort the array.
  • Initialize two pointers: one at the start of the array, the other at the end.
  • Move the pointers inward, checking if the sum of the numbers at the two pointers is equal to the target.

Time Complexity: O(n log n) (due to sorting)
Space Complexity: O(1) (additional space)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

Group Anagrams šŸ’›

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

There is no string in strs that can be rearranged to form "bat". The strings "nat" and "tan" are anagrams as they can be rearranged to form each other. The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

Approach 1: Group Anagrams by Sorting

Given a list of strings strs = ["eat", "tea", "tan", "ate", "nat", "bat"], the goal is to group the anagrams together. Here's the step-by-step approach:

  1. Sort Each String:
    For every string in the input list, sort its characters alphabetically. This ensures that anagrams will result in the same sorted string.

    Example:

    strs =        ["eat", "tea", "tan", "ate", "nat", "bat"]
sorted_strs = ["aet", "aet", "ant", "aet", "ant", "abt"]

  2. Group by Sorted Strings:
    Use a hashmap (dictionary) where the key is the sorted string, and the value is a list of strings that match that sorted string. Iterate through the strs list and group the original strings based on their sorted form.

    Result:

    result = [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Complexity Analysis

Time Complexity:
O(N Ɨ KLogK), where:

  • N is the number of strings in the input list.
  • K is the length of the longest string.
  • Sorting each string takes O(KLogK), and we do this for all N strings.

Space Complexity:
O(N Ɨ K), where:

  • The hashmap stores all the grouped anagrams, which requires space proportional to the total number of characters across all strings (N Ɨ K).

Approach 2: Group Anagrams Using Character Counts

Instead of sorting each string, we can use the frequency of each character as the key to group anagrams. Here's how it works:

  1. Count Character Frequencies:
    For each string in the input list, create a frequency count of its characters. Use a tuple of 26 integers (for each letter 'a' to 'z') to represent the frequency.

  2. Group by Frequency Keys:
    Use a hashmap (dictionary) where the key is the character frequency tuple, and the value is a list of strings that match that frequency.

    Result:

    result = [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Complexity Analysis

Time Complexity:
O(N Ɨ K), where:

  • N is the number of strings in the input list.
  • K is the length of the longest string.
  • Counting characters takes O(K), and we do this for all N strings.

Space Complexity:
O(N Ɨ K), where:

  • The hashmap stores all the grouped anagrams, which requires space proportional to the total number of characters across all strings (N Ɨ K).

This approach is often faster than sorting-based grouping for longer strings, as it avoids the overhead of sorting.

class Solution {
    private String getCharacterCountString(String str) {
        int[] count = new int[26];
        for (char ch : str.toCharArray()) {
            count[ch - 'a'] = count[ch - 'a'] + 1;
        }
        StringBuilder sb = new StringBuilder();
        for (int item : count) {
            sb.append("#");
            sb.append(item);
        }
        return sb.toString();
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            return new ArrayList();
        }
        Map<String, List<String>> ansMap = new HashMap<>();

        for (String str : strs) {
            String countString = getCharacterCountString(str);
            if (!ansMap.containsKey(countString)) {
                ansMap.put(countString, new ArrayList());
            }
            ansMap.get(countString).add(str);
        }

        return new ArrayList(ansMap.values());
    }
}

Top K Frequent Elements šŸ’›

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Approach 1: Store occurence in hashmap and then sort it

Approach 2: HashMap + Priority Queue

Encode and Decode Strings šŸ’›

Given an array of strings s[], you are required to create an algorithm in the encode() function that can convert the given strings into a single encoded string, which can be transmitted over the network and then decoded back into the original array of strings. The decoding will happen in the decode() function.

You need to implement two functions:

  1. encode(): This takes an array of strings s[] and encodes it into a single string.
  2. decode(): This takes the encoded string as input and returns an array of strings containing the original array as given in the encode method.

Note: You are not allowed to use any inbuilt serialize method.

Example 1:

Input: s = ["Hello","World"]
Output: ["Hello","World"]

Explanation: The encode() function will have the str as input, it will be encoded by one machine. Then another machine will receive the encoded string as the input parameter and then will decode it to its original form.

Example 2:

Input: s = ["abc","!@"]
Output: ["abc","!@"]

Explanation: The encode() function will have the str as input, here there are two strings, one is "abc" and the other one has some special characters. It will be encoded by one machine. Then another machine will receive the encoded string as the input parameter and then will decode it to its original form.

Constraints:

1<=s.size()<=100
1<=s[i].size()<=100
s[i] contains any possible characters out of the 256 ASCII characters.

Solution

class Solution {

    public String encode(String s[]) {
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length-1;i++) {
            sb.append(s[i]);
            sb.append('#');
        }
        sb.append(s[s.length-1]);
        return sb.toString();
    }

    public String[] decode(String s) {
        return s.split("#");
    }
}

Product of Array Except Self šŸ’›

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 105
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Problem: Product of Array Except Self

The task is to calculate a new array result such that each element at index i of the array result is the product of all the elements of the input array nums except the one at index i. You cannot use division, and the solution must run in (O(n)) time.

Approach 1: Using Prefix and Postfix Arrays

This approach calculates the prefix product and postfix product for each element, then combines them to get the result.

Explanation:

  1. Initialize Helper Arrays:

    • prefixProduct[i] holds the product of all elements before index i.
    • postfixProduct[i] holds the product of all elements after index i.

  2. Calculate Prefix Products:

    • Start with prefixProduct[0] = 1 (no elements before the first element).
    • For each index i, calculate: 
      prefixProduct[i] = prefixProduct[i-1] * nums[i-1];

  3. Calculate Postfix Products:

    • Start with postfixProduct[len-1] = 1 (no elements after the last element).
    • For each index i (from right to left): 
      postfixProduct[i] = postfixProduct[i+1] * nums[i+1];

  4. Combine Prefix and Postfix Products:

    • For each index i, calculate the result as: 
      ans[i] = prefixProduct[i] * postfixProduct[i];

  5. Time Complexity:

    • Prefix computation: (O(n)).
    • Postfix computation: (O(n)).
    • Final combination: (O(n)).
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] prefixProduct = new int[len];
        int[] postfixProduct = new int[len];
        int[] ans = new int[len];

        prefixProduct[0] = 1;
        postfixProduct[len - 1] = 1;

        for (int i = 1; i < nums.length; i++) {
            prefixProduct[i] = prefixProduct[i - 1] * nums[i - 1];
        }

        for (int i = nums.length - 2; i >= 0; i--) {
            postfixProduct[i] = postfixProduct[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < len; i++) {
            ans[i] = prefixProduct[i] * postfixProduct[i];
        }

        return ans;
    }
}

Approach 2: Optimized Solution Without Extra Space

This approach avoids using extra arrays for prefix and postfix products by calculating the result directly in one pass for prefix and one pass for postfix.

Explanation:

  1. Initialize the Result Array:

    • The result array will hold the prefix product in the first pass.

  2. Calculate Prefix Products:

    • Use a variable pre to keep track of the running prefix product.
    • For each index i, set: 
      result[i] = pre;
pre = pre * nums[i];

  3. Calculate Postfix Products:

    • Use a variable post to keep track of the running postfix product.
    • Traverse from right to left and update result as: 
      result[i] = result[i] * post;
post = post * nums[i];

  4. Time Complexity:

    • Prefix computation: (O(n)).
    • Postfix computation: (O(n)).
    • Space complexity: (O(1)) (ignoring output array).
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        int pre = 1, post = 1;

        for (int i = 0; i < nums.length; i++) {
            result[i] = pre; 
            pre = pre * nums[i];
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] = result[i] * post;
            post = post * nums[i];
        }

        return result;
    }
}

Key Differences Between the Approaches:

FeatureApproach 1Approach 2
Space Complexity(O(n)) (extra arrays)(O(1)) (no extra arrays)
ImplementationEasier to understandSlightly more optimized
PerformanceSimilar runtime (O(n))Similar runtime (O(n))

Valid Sudoku šŸ’›

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules.

Example 1:

sudoku

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.

Approach: Using HashMap for Sudoku Validation

This approach uses a HashMap to track seen characters in rows, columns, and sub-boxes while iterating through the Sudoku board.

class Solution {
    public boolean isValidSudoku(char[][] board) {
        final int N = 9;
    
        Map<String, Set<Character>> map = new HashMap<>();

        for(int i = 0; i < N; i++) {
            map.put("R" + i, new HashSet<>()); // Row
            map.put("C" + i, new HashSet<>()); // Column
            map.put("B" + i, new HashSet<>()); // Box
        }

        for(int r = 0; r < N; r++) {
            for(int c = 0; c < N; c++) {
                char ch = board[r][c];
                int box = r / 3 * 3 + c / 3;

                if(ch == '.') {
                    continue;
                }

                if(
                    map.get("R" + r).contains(ch) ||
                    map.get("C" + c).contains(ch) ||
                    map.get("B" + box).contains(ch)
                ) {
                    return false;
                }

                map.get("R" + r).add(ch);
                map.get("C" + c).add(ch);
                map.get("B" + box).add(ch);
            }
        }
        return true;
    }
}

Complexity Analysis:

Time Complexity: O(NĀ²), where N = 9 (constant board size). Iterates through each cell of the board once.

Space Complexity: O(NĀ²), for storing sets in the HashMap to track characters in rows, columns, and boxes.

Longest Consecutive Sequence šŸ’›

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

0 <= nums.length <= 105
-109 <= nums[i] <= 109

Approach 1: Sorting

This approach sorts the input array and finds the longest consecutive sequence by iterating through the sorted array. Consecutive numbers are counted, and the maximum sequence length is tracked.

Code:

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        
        int max = 1;
        int currentMax = 1;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] == nums[i - 1]) {
                continue;
            } else if (nums[i] == nums[i - 1] + 1) {
                currentMax++;
            } else {
                currentMax = 1;
            }
            max = Math.max(max, currentMax);
        }
        return max;
    }
}

Complexity Analysis:

  • Time Complexity: O(N log N), where N is the number of elements in the input array. This is due to the sorting step.
  • Space Complexity: O(1) (if sorting in place) or O(N) (if additional space is used for sorting).

Approach 2: Using HashSet

This approach leverages a HashSet to store all unique numbers from the array. By iterating through the set, the algorithm checks for consecutive sequences, starting with numbers that do not have a preceding number in the set.

Code:

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for(int num : nums) {
            set.add(num);
        }

        int longestSub = 1;
        for(int num : set) {
            if(set.contains(num - 1)) {
                continue;
            }

            int currentNum = num;
            int currentMax = 1;
            while(set.contains(currentNum + 1)) {
                currentNum++;
                currentMax++;
            }
            longestSub = Math.max(currentMax, longestSub);
        }
        return longestSub;
    }
}

Complexity Analysis:

  • Time Complexity: O(N), where N is the number of elements in the input array. Each number is processed once in the worst case.
  • Space Complexity: O(N), for the HashSet to store the elements.

Valid Palindrome šŸ’š

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: 
s = "A man, a plan, a canal: Panama"

Output:
true

Explanation:
"amanaplanacanalpanama" is a palindrome.

Example 2:

Input:  
s = "race a car"

Output:  
false

Explanation:
"raceacar" is not a palindrome.

Example 3:

Input:  
s = " "

Output:  
true

Explanation:
An empty string reads the same forward and backward, so it is a palindrome.

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters.

Approach 1: Two Pointer Approach (O(n) time complexity, O(1) space complexity)

Algorithm:

  1. Use two pointers, i starting from the beginning of the string and j from the end.
  2. Move the pointers towards each other while skipping non-alphanumeric characters.
  3. Convert the characters to lowercase and compare them.
  4. If any pair of characters don't match, return false.
  5. If the pointers cross each other without finding a mismatch, return true.

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we only use a constant amount of extra space.

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;

        while (i < j) { 
            char ch1 = Character.toLowerCase(s.charAt(i));
            char ch2 = Character.toLowerCase(s.charAt(j));

            // Skip non-alphanumeric characters
            if (!Character.isLetterOrDigit(ch1)) {
                i++;
                continue;
            }   
            if (!Character.isLetterOrDigit(ch2)) {
                j--;
                continue;
            }

            // Check for mismatch
            if (ch1 != ch2) {
                return false;
            }

            // Move pointers inward
            i++;
            j--;
        }

        return true;
    }
}

Explanation:

  • We initialize two pointers i and j at the beginning and end of the string.
  • For each pair of characters, we first skip non-alphanumeric characters and then compare the corresponding characters.
  • If they are not equal, we return false. If the loop completes without finding a mismatch, we return true.

Edge Cases:

  1. Empty string: An empty string is considered a palindrome.
  2. String with only non-alphanumeric characters: After removing the non-alphanumeric characters, an empty string is considered a palindrome.
  3. Mixed cases: The function converts all characters to lowercase before comparing them to ensure case insensitivity.

This solution ensures that we check the string efficiently and meet the problem's constraints.

Two Sum II Input Array Is Sorted šŸ’›

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
    numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
    The tests are generated such that there is exactly one solution.

Approaches:

1. Using Binary Search (O(n^2)):

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length-1;

        while(i<j){
            int sum = numbers[i] + numbers[j];
            if(sum < target) {
                i++;
            } else if(sum>target) {
                j--;
            } else {
                return new int[]{i+1, j+1};
            }
        }
        return null;
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

3Sum šŸ’›

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

Approaches:

[Naive Approach] Generating All Triplets ā€“ O(n^3) Time and O(1) Space

class Solution {
    public List<List<Integer>> threeSumBruteForce(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(triplet);
                        if (!res.contains(triplet)) {
                            res.add(triplet);
                        }
                    }
                }
            }
        }
        return res;
    }
}

Time Complexity: O(n^2)
Space Complexity: O(1)

HashSet - O(n^2) Time and O(n) Space

class Solution {
    public List<List<Integer>> threeSumHashSet(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            int target = -nums[i];
            Set<Integer> seen = new HashSet<>();
            for (int j = i + 1; j < nums.length; j++) {
                int complement = target - nums[j];
                if (seen.contains(complement)) {
                    result.add(Arrays.asList(nums[i], nums[j], complement));
                }
                seen.add(nums[j]);
            }
        }
        return new ArrayList<>(result);
    }
}

Time Complexity: O(n^2)
Space Complexity: O(n)

Two Pointer:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        for(int index = 0; index < nums.length-2; index++) {
            if(index == 0 || (index > 0 && nums[index] != nums[index-1])) {
                twoSumII(index, nums, result);
            }
        }
        return result;
    }

    public void twoSumII(int index, int[] nums, List<List<Integer>> result) {
        int sum = -nums[index];

        int start = index+1;
        int end = nums.length - 1;

        while(start < end) {
            int num1 = nums[start], num2 = nums[end];

            if(num1 + num2 < sum) {
                start++;
            } else if(num1 + num2 > sum) {
                end--;
            } else {
                result.add(Arrays.asList(nums[index], num1, num2));
                start++;
                end--;

                while (start < end && nums[start] == nums[start - 1]) {
                    start++;
                }
                while (start < end && nums[end] == nums[end + 1]) {
                    end--;
                }
            }
        }
    }
}

Time Complexity: O(NLogN + N2)
Space Complexity: O(1)

Container With Most Water šŸ’›

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

Approaches

Brute Force - O(N^2) Time and O(1) Space

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int n = height.length;

        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int area = (j - i) * Math.min(height[i], height[j]);
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }
}

Optimal Solution - O(N) Time and O(1) Space

class Solution {
    public int maxArea(int[] height) {
        int start = 0;
        int end = height.length -1;
        int maxArea = 0;
        while(start < end) {
            int area = (end-start) * Math.min(height[start], height[end]);

            maxArea = Math.max(area, maxArea);

            if(height[start] <= height[end]) {
                start++;
            } else {
                end--;
            }
        }
        return maxArea;
    }
}

Trapping Rain Water ā¤ļø

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

Approaches:

Brute Force

Effective Solution - O(N) Time and O(N) Space

public int trap(int[] height) {
    int total = 0;
    int n = height.length;
    int[] left = new int[n];
    int[] right = new int[n];
    left[0] = height[0];
    right[n - 1] = height[n - 1];
    for (int i = n - 2; i > 0; i--) {
        right[i] = Math.max(right[i + 1], height[i]);
    }
    for (int i = 1; i < n; i++) {
        left[i] = Math.max(left[i - 1], height[i]);
    }
    for (int i = 1; i < n - 1; i++) {
        int x = Math.min(left[i], right[i]) - height[i];
        if (x > 0) {
            total += x;
        }
    }
    return total;
}

Optimal Solution - O(N) Time and O(N) Space

class Solution {
    public int trap(int height[]) {
        int n = height.length;

        int left = 0;
        int right = n-1;

        int leftMax = height[left];
        int rightMax = height[right];

        int total = 0;

        while(left < right) {
            if (height[left] < height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                if (leftMax - height[left] > 0) {
                    total = total + leftMax - height[left];
                }
                left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                if (rightMax - height[right] > 0) {
                    total = total + rightMax - height[right];
                }
                right--;
            }
        }
        return total;
    }
}

Best Time to Buy And Sell Stock šŸ’š

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

Approaches

Brute Force - O(N^2) Time and O(1) Space

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        int n = prices.length - 1;

        for(int i=0; i < n-1; i++) {
            for(int j=i+1; j < n; j++) {
                int currentProfit = prices[j] - prices[i];
                profit = Math.max(profit, currentProfit);
            }
        }
        return profit;
    }
}

Optimal Force - O(N) Time and O(1) Space

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        int min=prices[0];
        int len = prices.length;

        for(int i=1;i<len;i++){
            min = Math.min( min, prices[i]);
            profit=Math.max(prices[i] - min, profit);
        }

        return profit;
    }
}

Longest Substring Without Repeating Characters šŸ’›

Longest Repeating Character Replacement šŸ’›

Permutation In String šŸ’›

Minimum Window Substring ā¤ļø

Sliding Window Maximum ā¤ļø

Greedy Algorithm

Shortest Job First (or SJF) CPU Scheduling

The shortest job first (SJF) or shortest job next, is a scheduling policy that selects the waiting process with the smallest execution time to execute next.

Given an array of integers bt of size n. Array bt denotes the burst time of each process. Calculate the average waiting time of all the processes and return the nearest integer which is smaller or equal to the output.

Note: Consider all process are available at time 0.

Input:
n = 5
bt = [4,3,7,1,2]
Output: 4
Explanation: After sorting burst times by shortest job policy, calculated average waiting time is 4.

T = [ 4, 3, 7, 1, 2 ]  
      p1 p2 p3 p4 p5


      p1  -->  0
      p5  -->  1
      p2  -->  2
      p1  -->  3
      p3  -->  4


    0 --- 1 --- 3 --- 6 --- 10 --- 13
       p4    p5    p2    p1     p3

Approach:

  1. Sort
import java.util.*;

class Solution {
    static int solve(int bt[] ) {
        if (bt==null || bt.length == 0) {
            return 0;
        }
        
        Arrays.sort(bt);
        int timer = 0;
        int sum = 0;
        
        for(int value: bt){
            sum+=timer;
            timer += value;
        }
        return sum/bt.length;
    }   
}

Time Complexity: O(nlog(n))
Auxiliary Space: O(1)

Source: GeeksForGeeks

Jump Game - I

Given a array of positive integers arr, where each element denotes the maximum length of jump you can cover. Find out if you can make it to the last index starting from the first index of the list, return true if you can reach the last index.

Examples:

Input: arr = [1, 2, 0, 3, 0, 0]
Output: true
Explanation: Jump 1 step from first index to second index. Then jump 2 steps to reach 4th index, and now jump 2 steps to reach the end.

class Solution {
    public boolean canReach(int[] arr) {
        
    }
}

Dynamic Programming

Dynamic Programming