DEV Community: shashi

Find missing in second array

shashi — Fri, 19 Apr 2024 06:45:19 +0000

Given two arrays a of size n and b of size m, the task is to find numbers which are present in the first array, but not present in the second array.

** Example 1:

Input:
n = 6, m = 5
a[] = {1, 2, 3, 4, 5, 10}
b[] = {2, 3, 1, 0, 5}
Output:
4 10
Explanation:
4 and 10 are present in first array, but not in second array.
Example 2:
Input:
n = 5, m = 5
a[] = {4, 3, 5, 9, 11}
b[] = {4, 9, 3, 11, 10}
Output:
5

Explanation:
Second array does not contain element 5.
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function findMissing() that takes array a, array b, integer n, and integer m as parameters and returns an array that contains the missing elements and the order of the elements should be the same as they are in array a.
Expected Time Complexity: O(n+m).
Expected Auxiliary Space: O(m).
Constraints:
1 ≤ n, m ≤ 105
-109 ≤ A[i], B[i] ≤ 109**

class Solution
{

    //Time :O(n +m) Space :O(m)
    ArrayList<Integer> findMissing(int a[], int b[], int n, int m)
    {
        Set<Integer> hSet=new HashSet<>();
        for(int i: b) hSet.add(i);

        ArrayList<Integer> ans=new ArrayList<>();
        for(int i: a) if(!hSet.contains(i)) ans.add(i);

        return ans;
    }
}

Count Pairs in an Array

shashi — Wed, 17 Apr 2024 08:51:21 +0000

Count Pairs in an Array

HardAccuracy: 48.25%Submissions: 24K+Points: 8

Given an array arr of n integers, count all pairs (arr[i], arr[j]) in it such that i*arr[i] > j*arr[j] **and **0 ≤ i < j < n.

Note: 0-based Indexing is followed.

Example 1:

Input :
n = 4
arr[] = {8, 4, 2, 1}
Output :
2
Explanation:
If we see the array after operations
[0*8, 1*4, 2*2, 3*1] => [0, 4, 4, 3]
Pairs which hold the condition i*arr[i] > j*arr[j] are (4,1) and (2,1), so in total 2 pairs are available.

Example 2:

Input :
n = 7
arr[] = {5, 0, 10, 2, 4, 1, 6}
Output:
5
Explanation :
Pairs which hold the condition i*arr[i] > j*arr[j] are (10,2), (10,4), (10,1), (2,1) and (4,1), so in total 5 pairs are there.

Your Task: **
You don’t need to read input or print anything. Your task is to complete the function **countPairs() which takes the array arr[] and its size **n **as inputs and returns the required result.

**Expected Time Complexity: **O(n*log(n))
**Expected Auxiliary Space: **O(n*log(n))

Constraints:
1 ≤ n *≤ **104
0 ≤ arr[i] *≤ **104

Topic Tags

Report An Issue

//User function Template for Java


//define a pair class 


class Solution {  

    //Time :O(n^2) space :O(1)
    static int countPairs1(int arr[], int n) 
    {
         // Your code goes here
         int c=0;
         for(int i=0;i<n;i++){
             for(int j=i+1; j<n ; j++){
                 if(i*arr[i] > j*arr[j]) c++;
             }
         }
         return c;
    }

    /*Time : O(n*(log(n)) Space : O(n*log(n))*/
    static int countPairs(int arr[], int n) 
    {
        //find the product of index and value store it in same array
        for(int i=0;i<n;i++)arr[i]*=i;

        return mergeSort(arr,0, n-1);
    }
    static int mergeSort(int[]arr, int l, int r){
        int count = 0;
        if(l<r){
            int mid = l+(r-l)/2;
            count += mergeSort(arr,l,mid);
            count += mergeSort(arr, mid+1,r);

            count += merge(arr,l,mid,r);
        }
        return count;
    }

    static int merge(int[]arr, int l, int mid, int r){
        int count = 0;

        int j = mid+1;

        /*  finding pair */
        for(int i=l; i<=mid; i++){

         while(j<=r && arr[i]>arr[j] ) j++;
          count+= (j-(mid+1));

        }


      /*calculate the size of left sub array & right sub array*/
        int n = mid-l+1;
        int m = r-mid;


    /*declare the left sub array and righ sub array*/
        int[]left = new int[n];
        int[]right = new int[m];


    /*copy the data from input array to left , right sub array*/
        for(int i=0;i<n;i++){
            left[i] = arr[l+i];
        }
        for(int i=0;i<m;i++){
            right[i] = arr[mid+i+1];
        }



        /*declare the iterator indx variables for input array, left, right sub array */
        int i=0;
        j = 0;
        int k = l;

        /*iterate untill out of  bounce */
        while(i<n && j<m){

            /*copyt the min element from right, left subarray to input array*/
            if(left[i]<=right[j]){
                arr[k++] = left[i++];
            }else{
                arr[k++] = right[j++];
            }
        }

        /*copyt the elements remaining from both the arrays*/
        while(i<n)arr[k++] = left[i++];
        while(j<m)arr[k++] = right[j++];

        return count;
    }

}

/*

Count Pairs in an Array
HardAccuracy: 48.25%Submissions: 24K+Points: 8
Given an array arr of n integers, count all pairs (arr[i], arr[j]) in it such that i*arr[i] > j*arr[j] and 0 ≤ i < j < n.

Note: 0-based Indexing is followed.

Example 1:

Input :
n = 4
arr[] = {8, 4, 2, 1}
Output :
2
Explanation:
If we see the array after operations
[0*8, 1*4, 2*2, 3*1] => [0, 4, 4, 3]
Pairs which hold the condition i*arr[i] > j*arr[j] are (4,1) and (2,1), so in total 2 pairs are available.
Example 2:

Input :
n = 7
arr[] = {5, 0, 10, 2, 4, 1, 6}
Output:
5
Explanation :
Pairs which hold the condition i*arr[i] > j*arr[j] are (10,2), (10,4), (10,1), (2,1) and (4,1), so in total 5 pairs are there.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countPairs() which takes the array arr[] and its size n as inputs and returns the required result.

Expected Time Complexity: O(n*log(n))
Expected Auxiliary Space: O(n*log(n))

Constraints:
1 ≤ n ≤ 104
0 ≤ arr[i] ≤ 104


*/

[623. Add One Row to Tree](https://leetcode.com/problems/add-one-row-to-tree/)

shashi — Tue, 16 Apr 2024 11:47:18 +0000

623. Add One Row to Tree

Solved

Medium

Topics

Companies

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.

Note that the root node is at depth 1.

The adding rule is:

Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
cur's original left subtree should be the left subtree of the new left subtree root.
cur's original right subtree should be the right subtree of the new right subtree root.
If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.

Example 1:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

Example 2:

Input: root = [4,2,null,3,1], val = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]

Constraints:

The number of nodes in the tree is in the range [1, 104].
The depth of the tree is in the range [1, 104].
-100 <= Node.val <= 100
-105 <= val <= 105
1 <= depth <= the depth of tree + 1

Seen this question in a real interview before?

1/5

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {


       return  dfs(root,val,depth,1,false);

    }
    public TreeNode dfs(TreeNode root, int val, int depth, int curr,boolean isLeft){


        if(root==null) {
            if(depth==1) root=new TreeNode(val);
            return root;
        }

        if(depth==1 && root!=null) {
                TreeNode newNode=new TreeNode(val);
                newNode.left=root;
                root=newNode;
                return newNode;
        }

        if(curr+1==depth){
                TreeNode newNode=new TreeNode(val);
                newNode.left=root.left;
                root.left=newNode;

                TreeNode newNode1=new TreeNode(val);
                newNode1.right=root.right;
                root.right=newNode1;

                return root;
            }

        dfs(root.left,val,depth,curr+1,true);
        dfs(root.right,val,depth,curr+1,false);
        return root;
    } 
}
/**

623. Add One Row to Tree
Solved
Medium
Topics
Companies
Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.

Note that the root node is at depth 1.

The adding rule is:

Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
cur's original left subtree should be the left subtree of the new left subtree root.
cur's original right subtree should be the right subtree of the new right subtree root.
If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.

Example 1:


Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]
Example 2:


Input: root = [4,2,null,3,1], val = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]

Constraints:

The number of nodes in the tree is in the range [1, 104].
The depth of the tree is in the range [1, 104].
-100 <= Node.val <= 100
-105 <= val <= 105
1 <= depth <= the depth of tree + 1
 */