1.Common elements
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.vector <int> commonElements (int A[], int B[], int C[], int n1, int n2, int n3){//code heremap<int,int> ump;for(int i=0;i<n1;i++)ump[A[i]]=1;for(int i=0;i<n2;i++){if(ump.find(B[i])!=ump.end()){ump[B[i]]=2;}}for(int i=0;i<n3;i++){if(ump.find(C[i])!=ump.end() && ump[C[i]]==2){ump[C[i]]=3;}}vector<int> ans;for(auto itr : ump){if(itr.second==3)ans.push_back(itr.first);}return ans;}
class Solution
{
public:
vector <int> commonElements (int A[], int B[], int C[], int n1, int n2, int n3)
{
//code here.
vector <int> v;
int i=0;
int j=0;
int k=0;int l=INT_MIN;
while(i<n1 && j<n2 && k<n3)
{
if(A[i]==B[j] && B[j]==C[k] && l!=A[i])
{
v.push_back(A[i]);
l=A[i];
i++;
}
else if(A[i]<B[j])
{
i++;
}else if(B[j]<C[k])
{
j++;
}
else
{
k++;
}
}
return v;
}};
3.First Repeating Element
Given an array arr[] of size n, find the first repeating element. The element should occurs more than once and the index of its first occurrence should be the smallest.
Example 1:
Input:
n = 7arr[] = {1, 5, 3, 4, 3, 5, 6}Output: 2
Explanation:
5 is appearing twice and its first appearence is at index 2 which is less than 3 whose first occuring index is 3.Example 2:
Input:
n = 4arr[] = {1, 2, 3, 4}Output: -1
Explanation:
All elements appear only once so answer is -1.O(n) Time & Space Solution
class Solution {// Function to return the position of the first repeating element.public static int firstRepeated(int[] arr, int n) {Map <Integer, Integer> counter = new HashMap<>();for(int x: arr){counter.put(x,counter.getOrDefault(x, 0)+1);}for(int i = 0; i < n; i++)if(counter.get(arr[i]) > 1)return i+1;return -1;}}
JAVA OPTIMIZED SOLUTION-
public static int firstRepeated(int[] a, int n) {
HashMap<Integer,Integer> hm = new HashMap<>();
int index =-1;
for(int i=0;i<n;i++){
if(hm.containsKey(a[i])){
hm.put(a[i] , hm.get(a[i])+1);
}else{
hm.put(a[i] , 1);}
}
for(int i=0;i<n;i++){
if(hm.containsKey(a[i])){
if(hm.get(a[i]) > 1){
index = i+1;
break;
}
}
}
return index;
}
4.Non-Repeating Element
Find the first non-repeating element in a given array arr of N integers.
Note: Array consists of only positive and negative integers and not zero.
Example 1:
Input : arr[] = {-1, 2, -1, 3, 2}
Output : 3
Explanation:-1 and 2 are repeating whereas 3 is the only number occuring once.Hence, the output is 3. Example 2:
Input : arr[] = {1, 1, 1}
Output : 0
int firstNonRepeating(int arr[], int n)
{
map<long long , size_t> m;
for(int i=0; i<n; i++){
m[arr[i]]++;
}
for(int i=0; i<n; i++){
if(m[arr[i]] == 1)
return arr[i];
}
return 0;
}const firstNonRepeating = (array, size) => {
const dupliceObjects = array.reduce((acc, curr)=> {
if (acc[curr]) {
acc[curr] = acc[curr] + 1; // if duplicates increment the count
} else {
acc[curr] = 1; // no duplicate
}
return acc;
}, {});
/*
let nonRepeatingElement = -1;
for (let i = 0; i < size; i++) {
if (dupliceObjects[array[i]] === 1) {
nonRepeatingElement = array[i];
break;
}
}
if (nonRepeatingElement === -1) {
console.log('element not found ', nonRepeatingElement);
} else {
console.log('first non repeating element ', nonRepeatingElement)
}
*/
let nonRepeatingElement = -1;
for (key in dupliceObjects) {
if (dupliceObjects[key] === 1) {
nonRepeatingElement = key;
break;
}
}
if (nonRepeatingElement === -1) {
const firstNonRepeating = (array, size) => {
const dupliceObjects = array.reduce((acc, curr)=> {
if (acc[curr]) {
acc[curr] = acc[curr] + 1; // if duplicates increment the count
} else {
acc[curr] = 1; // no duplicate
}
return acc;
}, {});
/*
let nonRepeatingElement = -1;
for (let i = 0; i < size; i++) {
if (dupliceObjects[array[i]] === 1) {
nonRepeatingElement = array[i];
break;
}
}
if (nonRepeatingElement === -1) {
console.log('element not found ', nonRepeatingElement);
} else {
console.log('first non repeating element ', nonRepeatingElement)
}
*/
let nonRepeatingElement = -1;
for (key in dupliceObjects) {
if (dupliceObjects[key] === 1) {
nonRepeatingElement = key;
break;
}
}
if (nonRepeatingElement === -1) {
console.log('element not found ', nonRepeatingElement);
} else {
console.log('first non repeating element ', nonRepeatingElement)
}
};
const array = [9, 4, 9, 6, 7, 4];
// const array = [-1, 2, -1, 3, 2];
firstNonRepeating(array, array.length);
