LeetCode, 𝐃𝐚𝐲-15/365-DSA-Coding 𝐉𝐨𝐮𝐫𝐧𝐞𝐲…Google Prep…

Aaqib Ali
2 min readJan 14, 2025

--

Today I Learned This Problem: Prefix Common Array

Problem Overview Day 15’s problem, “Prefix Common Array,” involves determining the number of common elements between two arrays A and B at each prefix. For every index i, we must count how many elements have appeared in both arrays from index 0 to i. This problem is excellent for practicing frequency counting and efficient data tracking.

Challenges Involved

  • Efficient Frequency Tracking: We need to count occurrences of elements in both arrays without redundant computations.
  • Simultaneous Iteration: Handling two arrays in parallel requires precise control to ensure accurate comparison.
  • Dynamic Counting: Updating the count of common elements in real-time as we iterate through the arrays.

Explanation The solution uses a frequency array to track how many times each number appears in both arrays. Here’s how it works:

  • Frequency Array: Keeps count of how many times each element has been seen.
  • Common Counter: Increments when an element appears in both arrays.
  • Result List: Stores the number of common elements at each prefix.

For every index i, we increment the frequency of the current elements from both arrays. If an element’s frequency reaches 2, it means it has appeared in both arrays, and we increase the common counter.

My Solution Approach

  1. Initialization:
  • Create a frequency array of size n + 1 initialized to 0.
  • Set a counter common to 0.
  • Prepare an empty list ans to store the results.

2. Iteration:

  • Loop through both arrays simultaneously.
  • Increment the frequency of the current elements.
  • If an element reaches a frequency of 2, increment common.

3. Result Collection:

  • Append the current value of common to ans after each iteration.

4. Return the Result:

  • Return the result list after completing the loop.

Python Code

class Solution:
def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
n = len(A)
freq = [0] * (n + 1)
ans = []
common = 0
for i in range(n):
freq[A[i]] += 1
if freq[A[i]] == 2:
common += 1
freq[B[i]] += 1
if freq[B[i]] == 2:
common += 1
ans.append(common)

return ans

Other Possible Solutions

  • Using Sets: Maintain two sets for A and B, updating and checking for common elements after each step. This is less efficient than the frequency array but easier to implement.
  • Hash Map Approach: Use a dictionary to handle elements beyond a limited range, which scales better for larger datasets.

Learnings

  • Improved understanding of frequency counting techniques.
  • Gained experience in efficiently handling two arrays in parallel.
  • Practiced real-time data tracking during iteration.

Real-Life Usage

  • Data Comparison: Comparing logs or datasets to find overlapping entries over time.
  • Real-Time Analytics: Tracking concurrent events in two data streams.

Final Thoughts Thank you for reading! If this explanation helped clarify the problem, feel free to share your thoughts or alternative solutions. Keep learning, coding, sharing, and growing!

--

--

No responses yet