DEV Community: Tisha Agarwal

LeetCode: Majority Element (Boyer-Moore Majority Voting Algorithm)

Tisha Agarwal — Mon, 21 Feb 2022 15:20:39 +0000

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

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

Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2

This is a EASY LEVEL question but it is very important.
It can easily be solved using two or three technics. But the main algorithm that we'll learn while solving it is Boyer-Moore Majority Voting Algorithm

To solve the question click here:(https://leetcode.com/problems/majority-element/)

The Boyer-Moore voting algorithm is one of the popular optimal algorithms which is used to find the majority element among the given elements that have more than N/ 2 occurrences. This works perfectly fine for finding the majority element which takes 2 traversals over the given elements, which works in O(N) time complexity and O(1) space complexity.

Approaches-
(1) Nested for-loop :
Time Complexity: O(N^2)
Space Complexity: O(1)

JAVA CODE:

public static int majorityElement(int[] nums) {

        int n=nums.length;
        int max=0,ele=nums[0];
        for(int i=0;i<nums.length;i++)
        {
            int count=0;
            for(int j=i;j<nums.length;j++)
            {
                if(nums[i]==nums[j])
                    count++;
            }
            if(count>max)
            {
                max=count;
                ele=nums[i];
            }
        }
        if(max>=(int)(n/2))
            return ele;

        return -1;
    }

(2) Sorting:
Time Complexity: O(NlogN)
Space Complexity: O(1)

JAVA CODE:

public static int majorityElement_m2(int nums[])
    {
            Arrays.sort(nums);
            return nums[nums.length/2];
    }

(3) HashMap:
Time Complexity: O(N)
Space Complexity: O(N)

JAVA CODE

public static int majorityElement_m3(int[] nums) {

        HashMap<Integer,Integer> hm=new HashMap<>();

        for(int i=0;i<nums.length;i++)
        {
            if(hm.containsKey(nums[i]))
                hm.put(nums[i] , hm.get(nums[i])+1);
            else
                hm.put(nums[i],1);
        }
        int answer =0;
     for (Map.Entry<Integer, Integer> entry : hm.entrySet())
     {
         if(entry.getValue()>nums.length/2)
         {
             answer = entry.getKey();
         }
     }
    return answer;
    }

(4)Boyer-Moore Majority Voting Algorithm:
Time Complexity: O(N)
Space Complexity: O(1)

JAVA CODE

public static int majorityElement_m4(int[] nums) {
        int ans=nums[0];
        int count=1;
        for(int i=1;i<nums.length;i++)
        {
                if(nums[i]==ans)
                    count++;
                else
                    count--;

        if(count==0)
        {
             ans=nums[i];
            count=1; 
        }

        }
        return ans;

    }

LeetCode: Count and Say

Tisha Agarwal — Sun, 20 Feb 2022 09:12:30 +0000

Question link

It's a MEDIUM LEVEL question. At first I found is tough but after going through the question thrice, I understood the concept.

So, before moving on to my question, I just wanna tell that this question can be done using 2 methods-
(1) Recursion (Optimize method)
(2) For-loop

For solving this question, I haven't used recursion. Instead I used for-loop method as it helped me in understanding the concept more clearly.

JAVA CODE

import java.util.*;
public class Count_and_Say {
    public static void main(String[] args) throws Exception
    {
        Scanner sc=new Scanner(System.in);
        System.out.print("Enter the value of n: ");
        int n=sc.nextInt();
        String s=countAndSay(n);
        System.out.println(s);
    }
    public static String countAndSay(int n) {
        String str="1";

        for(int i=2;i<=n;i++)
        {
            StringBuilder temp=new StringBuilder();
            char prev=str.charAt(0);
            int counter=1;
            for(int j=1;j<str.length();j++)
            {
                char ch=str.charAt(j);
                if(ch!=prev)
                {
                   temp.append(counter).append(prev);
                    prev=ch;
                    counter=1;
                }
                else
                {
                    counter++;
                }
            }
                temp.append(counter).append(prev);
                str=temp.toString();
            }

        return str;
    }
}

Why String is Immutable in JAVA? What exactly does it mean?

Tisha Agarwal — Mon, 14 Feb 2022 20:32:14 +0000

So recently I came across the question, why are Strings Immutable in java?
Before discussing on this, I would first like to tell What are Immutable strings?

Immutable simply means unmodifiable or unchangeable. Once String object is created its data or state can't be changed but a new String object is created.

Before going through this article, I recommend to first know about String Constant Pool

This is how String works:

String str = new String("Tisha");

This, as usual, creates a string containing "Tisha" and assigns it a reference str.

  str = str.concat(" Agarwal");

This appends a string " Agarwal" to str. But wait, how is this possible, since String objects are immutable? Well to your surprise, it is.
When the above statement is executed, the VM takes the value of String str, i.e. "Tisha" and appends " Agarwal", giving us the value "Tisha Agarwal". Now, since Strings are immutable, the VM can’t assign this value to str, so it creates a new String object, gives it a value "Tisha Agarwal", and gives it a reference str.

Why are strings Immutable?

Let's understand this with the help of an example:

String chocolate1="KitKat"; String chocolate2="KitKat"; String chocolate3="KitKat";

So what's happening?
In this a object of KitKat is created inside String Constant pool and all three variables chocolate1 , chocolate2 , chocolate3 are pointing to it.

Now if we change cholocate3 to MilkyBar
chocolate3=MilkyBar;

Suppose if the string were mutable then without creating a new object the value of chocolate3 would have changed from KitKat to MilkyBar.But don't you think this would also change the value of chocolate1 and chocolate2from KitKat to MilkyBar as shown in the above diagram, these 3 were pointing to the same object.

So, that's why Strings are Immutable,
from the above example, now the chocolate3 will create a different object and will point to it.

Point to Remember

Strings are Immutable in Java because String objects are cached in String pool. Since cached String literals are shared between multiple persons there is always a risk, where one person's action would affect all other persons.

String Constant Pool (Storage of Strings)

Tisha Agarwal — Mon, 14 Feb 2022 13:51:23 +0000

A string constant pool is a separate place in the heap memory where the values of all the strings which are defined in the program are stored.

Two ways to create string object:

1) String s1=new String("Tisha");
If we create a string like this, then it creates two objects in the memory. One is in Heap Area and the other is in string constant pool.

2) String s2="Anam";
In this only one object is created i.e. inside string constant pool.

That is why it is recommended to make string objects like this: String s2="Anam";, as only one object this created.
More the number of objects, more the project will become heavy.
If the project becomes heavy then it will slow down.

Interview question:

Can Garbage Collection occur in string constant pool?

String objects which are in the string pool will not be garbage collected because a reference variable internally is maintained by JVM for each string literal object. Other String objects will be garbage collected if you don't have reference to it in your program execution.

Special Cases
Suppose if we create two strings str1 and str2
String str1=new String("Alex");--------------->2 objects are created
String str2=new String ("John");-------------->2 objects are created

Now if we create one more string with the same string literal as str1 so in that case only one object will be created in heap area.
String constant pool(SCP) will check if that literal is inside it or not. If the literal "Alex" is present inside SCP then it will not create another literal with the same name. Hence only one object is created.
String str3=new String("Alex");----------------->1 object created

Now if we create string,
String str4="Simran";-------------->1 object created inside SCP

To understand it better, let's create more strings and see where their objects are being created- in heap area or in string constant memory?

String str5="Alex";----------->No objects are created
str5 will not create any objects because SCP will first check that whether "Alex" is already present inside it or not.
Since in this case "Alex" is already in SCP so no objects will be created. And str5 will start pointing to the previous "Alex" that existed inside String constant pool(SCP)

str6="Alex";
In this case str6 and str5 both will point to "Alex" inside SCP.

Points to remember:

If new keyword is used to create string then object is not only created in String Constant Pool but also in Heap Area.
If we create strings like String S="WONDERFUL" , then SCP checks whether the string literal is already present in SCP or not.
If it is not present the only 1 object is created inside String Constant Pool(SCP)
If same literal object is present inside string constant pool (SCP)
then instead of creating new object with the same literal, it points to the existing object.

Maximum Subarray Sum

Tisha Agarwal — Thu, 10 Feb 2022 19:33:13 +0000

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.

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

To solve this question click here:(https://leetcode.com/problems/maximum-subarray/)

Though it is a EASY LEVEL question but is really very important.

Brute force Approach:
Time Complexity: O(n^3)

C++ CODE:

#include<iostream>
#include<climits>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
      cin>>arr[i];
    int maxSum=INT_MIN;
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<n;j++)
        {
            int sum=0;
            for(int k=i;k<=j;k++)
                sum+=arr[k];
            maxSum=max(sum,maxSum);
        }
    }
    cout<<maxSum<<endl;
    return 0;
}

This question can be solved in an optimized way by using Kadane Algorithm.
The simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array. And keep track of maximum sum contiguous segment among all positive segments

C++ CODE:

#include<iostream>
#include <climits>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    cin>>arr[i];

   int currSum=0;
   int maxSum=INT_MIN;
   for(int i=0;i<n;i++)
   {
       currSum+=arr[i];
       if(currSum<0)
           currSum=0;
       maxSum=max(maxSum,currSum);
   }
   cout<<maxSum<<endl;
    return 0;
}

Subarray with 0 sum

Tisha Agarwal — Thu, 10 Feb 2022 15:18:01 +0000

Given an array of positive and negative numbers. Find if there is a subarray (of size at-least one) with 0 sum.

Example 1:
Input:
5
4 2 -3 1 6
Output:
Yes
Explanation:
2, -3, 1 is the subarray
with sum 0.

This is similar to the previous question Subarray sum equals k but this is EASY compared to that.

To solve this question click here:(https://practice.geeksforgeeks.org/problems/subarray-with-0-sum-1587115621/1/)

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

JAVA CODE

public static boolean subArrayExists(int arr[],int n)
    {
        for(int i=0;i<n;i++)
        {
            int sum=0;
            for(int j=i;j<n;j++)
            {
                sum+=arr[j];
                if(sum==0)
                  return true;

            }
        }
        return false;
    }

Approach 2:
This is similar to the previous subarray question that we solved.
Time Complexity: O(n)

JAVA CODE

  static boolean findsum(int arr[],int n)
    {
        //Your code here
        HashMap<Integer,Integer> hm=new HashMap<>();
        hm.put(0,1); // it is imp to put 0 initially in the hashmap
        int sum=0;
        for(int i=0;i<n;i++)
        {
            sum+=arr[i];
            if(hm.containsKey(sum))
                return true;

            hm.put(sum,hm.getOrDefault(sum,0)+1);
        }
        return false;
    }

Approach 3:
We have used HashSet in this as their is no need to use HashMap since we have no use of storing values in key, pair
Time Complexity: O(n)

JAVA CODE

public static boolean subArrayExists(int arr[],int n)
    {
         //declare a set data structure
         HashSet<Integer> res=new HashSet<>();
         int sum=0;

         for(int i=0;i<n;i++)
         {
             res.add(sum);//in first step it will add 0
             sum+=arr[i];
             if(res.contains(sum))
                 return true;
         }
         return false;

    }

Subarray Sum Equals K

Tisha Agarwal — Thu, 10 Feb 2022 13:51:57 +0000

Given an array of integers arr and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:
Input: arr = [1,1,1], k = 2
Output: 2

Example 2:
Input: arr = [1,2,3], k = 3
Output: 2

To solve this question click here:(https://leetcode.com/problems/subarray-sum-equals-k/)

So this is a MEDIUM LEVEL question. When I read this question then I knew that I have solved similar question in the past but still I couldn't solve this on my own. But after searching for a while I came across 3 approaches.
Brute Force---------------------------->Optimized
O(n^3)------------O(n^2)---------------O(n)

Approach 1:
So this is really very simple approach, in this we just need to run 3 nested loops and then calculate the sum of each subarray and check it with the target(k).

JAVA CODE:

public static int subaaray(int arr[],int n,int X)
    {
        int ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                int sum=0;
                for(int k=i;k<=j;k++)
                {
                    sum+=arr[i];
                }
                if(sum==X)
                   ans++;
            }
        }
        return ans;
    }

Approach 2:
In this we just removed the last for loop and calculated the sum inside j loop itself.

JAVA CODE:

public static int subaaray(int arr[],int n,int X)
    {
        int ans=0;
        for(int i=0;i<n;i++)
        {
            int sum=0;
            for(int j=i;j<n;j++)
            {
                sum+=arr[i];
                if(sum==X)
                   ans++;
            }
        }
        return ans;
    }

Approach 3:(Optimized)
In this we used HashMap to store the cumulative sum of the array.
Time Complexity: O(n)

JAVA CODE:

public static int subarray(int arr[],int n,int k)
    {
        HashMap<Integer,Integer> hm=new HashMap<>();
        hm.put(0,1); // it is imp to put 0 initially in the hashmap
        int ans=0,sum=0;
        for(int i=0;i<n;i++)
        {
            sum+=arr[i];
            if(hm.containsKey(sum-k))
                ans+=hm.get(sum-k);

            hm.put(sum,hm.getOrDefault(sum,0)+1);
        }
        return ans;

    }

Longest Consecutive Sequence

Tisha Agarwal — Sun, 06 Feb 2022 12:58:49 +0000

Given an array of positive integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

Example 1:
Input:
N = 7
a[] = {2,6,1,9,4,5,3}
Output:
6
Explanation:
The consecutive numbers here
are 1, 2, 3, 4, 5, 6. These 6
numbers form the longest consecutive
subsequence.

It is a MEDIUM LEVEL question, asked in Amazon,Walmart, Microsoft.

To solve this question click here:(https://practice.geeksforgeeks.org/problems/longest-consecutive-subsequence2449/1)

Approach 1:
It can be solved if we first sort the array and then find the longest subsequence. Write your code while keeping in mind that the elements can repeat.
This approach is not that efficient as the Time Complexity is O(nlog n+n) as to sorting algorithm will take time of nlogn.

Approach 2:
In second method I used HashSet to:
-remove duplicate elements from the array.
-to find the starting element of the sequence.
Time Complexity: O(n)
Space Complexity: O(n)

JAVA CODE

import java.util.*;
class LongestConsecutiveSeq{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the size of the array:");
        int n=sc.nextInt();
        int[] arr=new int[n];
        System.out.println("Enter the elements of the array:");
        for(int i=0;i<n;i++)
        {
            arr[i]=sc.nextInt();
        }
        System.out.println(findLongestConseqSubseq(arr,n));
    }
    static int findLongestConseqSubseq(int arr[], int n)
    {
        //creating hashSet to remove duplicacy
        HashSet<Integer> st=new HashSet<>();

        for(int i=0;i<n;i++)
            st.add(arr[i]);

        int ans=0,c=1;
        for(int i=0;i<n;i++)
        {
            c=1;
            if(!st.contains(arr[i]-1))
            {
                int val=arr[i]+1;
                while(st.contains(val))
                {
                    val++;
                    c++;
                }
                ans=Math.max(ans,c);
            }
        }
        return ans;
    }
}

Rearrange array in alternating positive & negative items with O(1) extra space

Tisha Agarwal — Sat, 05 Feb 2022 10:27:32 +0000

Given an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and vice-versa maintaining the order of appearance.
Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.

Examples :

Input: arr[] = {1, 2, 3, -4, -1, 4}
Output: arr[] = {-4, 1, -1, 2, 3, 4}

Input: arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}
output: arr[] = {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0}

Asked in Amazon

At even position: negative numbers
At odd position: positive numbers

i--> It will find the negative element in the array
j--> It will find the positive element in the array

JAVA CODE

import java.util.*;
public class RearrangeArrayInAlterPos {
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the size of the array:");
        int n=sc.nextInt();
        int[] arr=new int[n];
        System.out.println("Enter the elements of the array:");
        for(int i=0;i<n;i++)
        {
            arr[i]=sc.nextInt();
        }
        reArrange(arr, n);
    }
    //doing right rotate to shift the elements to the right
    //this is done to maintain the order of the elements
    public static void rotate(int arr[],int start,int end)
    {
        int temp=arr[end];
        for(int i=end-1;i>=start;i--)
        {
            arr[i+1]=arr[i];
        }
        arr[start]=temp;
    }
    public static void reArrange(int arr[],int n)
    {
        int i=0,j=0,k=0;
        while(i<n && j<n && k<n)
        {
            if(k%2==0)//if k is even
            {
                if(arr[k]>=0)
                {
                    i=k; j=k;
                    while(i<n && arr[i]>=0)
                       i++;
                    if(i>=n) break;
                    else
                       rotate(arr,j,i);
                }
            }
            else{
                if(arr[k]<0)
                {
                    i=k;
                    j=k;
                    while(j<n && arr[i]<0)
                       j++;
                    if(j>=n) break;
                    else
                    rotate(arr,i,j);
                }
            }
            k++;

        }
        for(int l=0;l<n;l++)
           System.out.print(arr[l]+" ");

    }

}

Merge Intervals

Tisha Agarwal — Fri, 04 Feb 2022 21:08:28 +0000

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

To solve the question click here:(https://leetcode.com/problems/merge-intervals/)

The new thing that I learned in this question is about comparator interface in java. Using a comparator, we can sort the elements based on data members. For instance, it may be on roll no, name, age, or anything else.

In this question, I used comparator to sort the intervals according to the 1st interval.
Arrays.sort(intervals,(o1,o2)->{ return o1[0]-o2[0]; });
For eg:[2,4] [1,5] [7,19] [6,7] ------->[1,5] [2,4] [6,7] [7,19]

Approach 1:
Using Stack method

First I have created a stack and pushed the first interval in the stack.([1,3] is pushed in the stack st)
Then I iterated the loop from 2nd interval to the end of the array.

JAVA CODE

 public static void merge(int[][] intervals){

        Arrays.sort(intervals,(o1,o2)->{
            return o1[0]-o2[0];
        });

        Stack<int[]> st=new Stack<>();
        st.push(intervals[0]);//[1,3] is pushed in the stack

        for(int i=1;i<intervals.length;i++)
        {
            int[] current=intervals[i];
            int[] last_inserted=st.peek();
             if(current[0]<=last_inserted[1])
             {
                 st.pop();
                 st.push(new int[]{last_inserted[0],Math.max(last_inserted[1],current[1])});
             }
             else{
                 st.push(current);
             }
        }
        // Stack<int[]> res=new Stack<>();
        // while(st.size()>0)
        // {
        //     res.push(st.pop());
        // }
        // while(res.size()>0)
        // {
        //     System.out.println(res.pop());
        // }
        int[][] res = new int[st.size()][2];
        st.toArray(res);
        System.out.println("----------");
        for(int i=0;i<res.length;i++)
        {
          System.out.print("["+res[i][0]+",");
          System.out.print(res[i][1]+"]"+" ");
        }
    }

Approach 2:
Used ArrayList to solve the problem in Space Complexity: O(n)

JAVA CODE

import java.util.*;
class merge_intervals{

    public static void main(String[] args) throws Exception
    {
        Scanner sc=new Scanner(System.in);
        System.out.print("Enter the number of elements: ");
        int n=sc.nextInt();
        int[][] arr=new int[n][2];

        for(int i=0;i<n;i++)
        {
            arr[i][0]=sc.nextInt();
            arr[i][1]=sc.nextInt();
        }
        merge(arr);
    }
public static void merge(int[][] intervals)
    {
        Arrays.sort(intervals,(o1,o2)->{
            return o1[0]-o2[0];
        });
        ArrayList<int[]> ans=new ArrayList<>();

        int start=intervals[0][0];// start=1
        int last=intervals[0][1]; //end=3

        for(int i=1;i<intervals.length;i++)
        {
            if(intervals[i][0]<=last && intervals[i][0]>=start)
            {
                last=Math.max(last,intervals[i][1]);
            }
            else
            {
                ans.add(new int[]{start,last});
                start=intervals[i][0];
                last=intervals[i][1];
            }
        }
        ans.add(new int[]{start,last});
        int[][] res=new int[ans.size()][2];
        ans.toArray(res);
        System.out.println("-----------------");
        for(int i=0;i<ans.size();i++)
        {
            System.out.print("["+res[i][0]+",");
            System.out.print(res[i][1]+"]"+" ");
        }
    }
}

Factorial of a large Number

Tisha Agarwal — Thu, 03 Feb 2022 20:08:28 +0000

Given an integer N, find its factorial.

Example 1:
Input: N = 5
Output: 120
Explanation : 5! = 1*2*3*4*5 = 120

Example 2:
Input: N = 10
Output: 3628800
Explanation :
10! = 1*2*3*4*5*6*7*8*9*10 = 3628800

To solve this question click here:(https://practice.geeksforgeeks.org/problems/factorials-of-large-numbers2508/1#);

Asked in companies like Adobe, BrowserStack, MakeMyTrip, Microsoft, Philips, Samsung

It is a MEDIUM LEVEL question, you must have calculated factorial of a number. But this question is a bit different, in this we have to calculate factorial of a large number.

Factorial of large numbers cannot be stored in int or long or long long. So in this case we use ArrayList or LinkedList to solve the question.

JAVA CODE

static ArrayList<Integer> factorial(int N){
        //code here
        ArrayList<Integer> res=new ArrayList<>();
        res.add(0,1); //adding 1 in the arraylist
        int size=1;
        int carry=0,val=2;

        while(val<=N)
        {
            for(int i=size-1;i>=0;i--)
            {
                int temp=res.get(i)*val + carry;
                //store the last digit at index and add remaining to carry
                res.set(i,temp%10);
                //update carry
                carry=temp/10;
            }
            while(carry!=0)
            {
                res.add(0,carry%10);
                carry=carry/10;
                size++;
            }
            val++;

        }
        return res;
    }

Common Element in 3 sorted array

Tisha Agarwal — Tue, 01 Feb 2022 16:24:47 +0000

Given three arrays sorted in increasing order. Find the elements that are common in all three arrays.
Note: can you take care of the duplicates without using any additional Data Structure?

Example 1:
Input:
n1 = 6; A = {1, 5, 10, 20, 40, 80}
n2 = 5; B = {6, 7, 20, 80, 100}
n3 = 8; C = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20 80
_Explanation: 20 and 80 are the only
common elements in A, B and C.
_
Example 2:
Input:
_n1=3; A={3, 3, 3}
n2=3; B={3, 3, 3}
n3=3; C={3, 3, 3}
_Output: 3

This question was asked in companies like MAQ Software, Microsoft ,VMWare

To solve this question click here:(https://practice.geeksforgeeks.org/problems/common-elements1132/1#)

Approach 1:
Time Complexity: O(n1+n2+n3)
Space Complexity: O(1)
In this we have used three pointer i, j, k to iterate through the 3 sorted array.

import java.util.*;

public class commonEle_in_3sorted {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n1: ");
        int n1 = sc.nextInt();
        System.out.print("Enter n2: ");
        int n2 = sc.nextInt();
        System.out.print("Enter n3: ");
        int n3 = sc.nextInt();
        int[] A = new int[n1];
        int[] B = new int[n2];
        int[] C = new int[n3];
        System.out.println("Enter the elements of the array A: ");
        for (int i = 0; i < n1; i++) {
            A[i] = sc.nextInt();
        }
        System.out.println("Enter the elements of the array B: ");
        for (int i = 0; i < n2; i++) {
            B[i] = sc.nextInt();
        }
        System.out.println("Enter the elements of the array C: ");
        for (int i = 0; i < n3; i++) {
            C[i] = sc.nextInt();
        }
        M1commonElement(A, B, C, n1, n2, n3);
    }

    public static void M1commonElement(int A[], int B[], int C[], int n1, int n2, int n3) {
        int i = 0, j = 0, k = 0;
        ArrayList<Integer> al = new ArrayList<>();
        while (i < n1 && j < n2 && k < n3) {
            if (A[i] == B[j] && A[i] == C[k]) {
                al.add(A[i]);// common element
                int ele = A[i];
                // to remove duplicacy
                while (i<n1 && A[i]==ele)
                    i++;
                while (j<n2 && B[j] == ele)
                    j++;
                while (k<n3 && C[k] == ele)
                    k++;
            } 
            else if (A[i] < B[j])
                i++;
            else if (B[j] < C[k])
                j++;
            else
                k++;

        }
        for (int ele : al) {
            System.out.println(ele);
        }
    }

Approach 2:
Time Complexity: O(n1+n2+n3)
Space Complexity: O(n1+n2+n3)
In this we have use HashMap to store the three sorted array. And then we have again iterated through the loop and checked if that element is present in the HashMap (hm1,hm2,hm3) or not.

 public static void M2commonElement(int A[], int B[], int C[], int n1, int n2, int n3) {
        HashMap<Integer, Integer> hm1 = new HashMap<>();
        HashMap<Integer, Integer> hm2 = new HashMap<>();
        HashMap<Integer, Integer> hm3 = new HashMap<>();
        for (int i = 0; i < n1; i++)
            hm1.put(A[i], i);
        for (int i = 0; i < n2; i++)
            hm2.put(B[i], i);
        for (int i = 0; i < n3; i++)
            hm3.put(C[i], i);

        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n1; i++) {
            if (hm1.containsKey(A[i]) && hm2.containsKey(A[i]) && hm3.containsKey(A[i])) {
                arr.add(A[i]);
                hm1.remove(A[i]);
            }
        }
        for (int ele : arr)
            System.out.print(arr);
    }