JAVA | Running | EASY & FAST | HashMap Frequency | Explained in detail
IntuitionApproachHere’s the approach for solving the problem of finding the intersection of all rows in a 2D array (nums):Problem ExplanationGiven a 2D array nu
# Intuition
![Screenshot 2025-01-27 094510.png](https://assets.leetcode.com/users/images/861792b1-9e0c-4fe9-a427-e68578042efd_1737951360.5100896.png)

<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
Here’s the approach for solving the problem of finding the intersection of all rows in a 2D array (`nums`):

---

### **Problem Explanation**
Given a 2D array `nums`, find the elements that are present in every row of `nums`. The result should be a sorted list of these elements.

---

### **Approach**

1. **Use a HashMap to Track Frequencies:**
   - Traverse through all rows and track how many rows each element appears in using a `HashMap`.
   - For each element in a row, increment its count in the map.

2. **Filter Elements Present in All Rows:**
   - After building the `HashMap`, iterate over its entries.
   - If an element’s count matches the total number of rows (`m`), it means the element is present in every row.

3. **Sort the Result:**
   - Collect all elements that are present in every row into a list.
   - Sort the list before returning it as the final result.

---

### **Steps**

1. **Initialization:**
   - Create a `HashMap` to store the frequency of each element across all rows.
   - Initialize a `List` to hold the result.

2. **Traverse the 2D Array:**
   - For each row in `nums`:
     - Iterate through its elements.
     - If the element is already in the `HashMap`, increment its frequency.
     - Otherwise, add it to the map with an initial count of `1`.

3. **Filter and Collect Results:**
   - Iterate through the entries of the `HashMap`.
   - If the frequency of an element equals the number of rows (`m`), add it to the result list.

4. **Sort the Result List:**
   - Sort the result list in ascending order.

5. **Return the Result:**
   - Return the sorted list as the final output.

---

### Example Walkthrough

#### Input:
```java
nums = [
    [1, 2, 3],
    [4, 5, 2],
    [6, 2, 7]
]
```

#### Execution:

1. **Initialize `HashMap`:**
   - Start with an empty map: `{}`.

2. **First Row `[1, 2, 3]`:**
   - Add `1`, `2`, `3` to the map: `{1: 1, 2: 1, 3: 1}`.

3. **Second Row `[4, 5, 2]`:**
   - Increment count for `2` and add `4`, `5`: `{1: 1, 2: 2, 3: 1, 4: 1, 5: 1}`.

4. **Third Row `[6, 2, 7]`:**
   - Increment count for `2` and add `6`, `7`: `{1: 1, 2: 3, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1}`.

5. **Filter Results:**
   - Only `2` appears in all 3 rows (`frequency == 3`).

6. **Sort and Return:**
   - Result list: `[2]`.

#### Output:
```java
[2]
```

---

### Complexity Analysis

#### **Time Complexity:**
1. **Building the HashMap:**
   - Each element in `nums` is processed once. Let \( n \) be the total number of elements across all rows. This step takes \( O(n) \).

2. **Filtering Results:**
   - Iterating through the `HashMap` takes \( O(k) \), where \( k \) is the number of unique elements.

3. **Sorting the Result:**
   - Sorting the final list takes \( O(x \log x) \), where \( x \) is the size of the result list.

**Total Time Complexity:**
\[
O(n + k + x \log x)
\]
In the worst case, \( k = n \) and \( x = k \), making the complexity \( O(n \log n) \).

#### **Space Complexity:**
1. **HashMap:**
   - Stores up to \( k \) unique elements. \( O(k) \).

2. **Result List:**
   - Stores up to \( k \) elements. \( O(k) \).

**Total Space Complexity:** \( O(k) \).

---

- This approach ensures efficiency by processing each element once and using a single map to track frequencies.

# Complexity
Let’s analyze the **time complexity** and **space complexity** of the given solution:

---

### Time Complexity:

#### 1. **Building the HashMap:**
- The outer loop iterates through each subarray in `nums`, and the inner loop iterates through the elements of the current subarray.
- Let \( n \) be the total number of elements across all subarrays (i.e., \( n = \text{sum of lengths of all subarrays} \)).
- Each element is processed once to either insert or update its frequency in the `HashMap`.
- **Time for this step:** \( O(n) \).

#### 2. **Iterating Through the HashMap:**
- The `HashMap` contains at most \( n \) keys (one for each distinct number in the input).
- For each key, we check its frequency to see if it matches the number of subarrays \( m \). This operation takes \( O(k) \), where \( k \) is the number of distinct elements in the input.
- **Time for this step:** \( O(k) \).

#### 3. **Sorting the Result List:**
- After filtering the elements that appear in all \( m \) subarrays, the resulting list \( a \) (with size \( x \)) is sorted.
- **Time for this step:** \( O(x \log x) \), where \( x \leq k \).

---

#### Total Time Complexity:
The total time complexity is:
\[
O(n) + O(k) + O(x \log x)
\]
- In the worst case, all elements are distinct and appear in all subarrays, so \( k = n \) and \( x = k \).
- Thus, the worst-case time complexity simplifies to:
\[
O(n + n \log n) = O(n \log n)
\]

---

### Space Complexity:

#### 1. **HashMap:**
- The `HashMap` stores frequencies of up to \( k \) distinct elements, which requires \( O(k) \) space.

#### 2. **Result List:**
- The result list stores at most \( k \) elements, so it requires \( O(k) \) space.

#### 3. **Other Variables:**
- A few auxiliary variables (e.g., `a`, loop counters) use \( O(1) \) space.

---

#### Total Space Complexity:
The total space complexity is:
\[
O(k)
\]
where \( k \) is the number of distinct elements in the input.

---

### Final Complexity:
- **Time Complexity:** \( O(n \log n) \)
- **Space Complexity:** \( O(k) \)

# Code
```java []
class Solution {
    public List<Integer> intersection(int[][] nums) 
    {
        HashMap<Integer,Integer> h=new HashMap<>();
        List<Integer> a=new ArrayList<>();
        int m=nums.length;//number of arrays
        for(int i=0;i<m;i++)//iterating array to array
        {
            for(int j=0;j<nums[i].length;j++)//iterating through array elements
            {
                if(h.containsKey(nums[i][j]))
                {
                    h.put(nums[i][j],h.get(nums[i][j])+1);//taking frequency
                }
                else
                {
                    h.put(nums[i][j],1);
                }
            }
        }
        for(Map.Entry er:h.entrySet())
        {
            if((int)er.getValue()==m)//if freq is equal to number of arrays
            {
                a.add((int)er.getKey());//then,add in list
            }
        }
        Collections.sort(a);//sorting the list
        return a;
    }
} // please upvote ;)
```
![Screenshot 2025-01-15 234234.png](https://assets.leetcode.com/users/images/18230af7-9861-4705-ba57-8669f2c70b6a_1737951394.1769967.png)

['Array', 'Hash Table', 'Sorting', 'Counting', 'Java']