DSAAGP36 - Editorial

editorial
, ,
1

Problem Link - Frequency of elements using Hashing in Hashing

Problem Statement:

You are given an integer N and an array A containing N integers. For each element in the array, you have to output its frequency in the array using Hashing.

Approach:

  • Find the maximum element in the array.
  • Declare a Hash array of size max_element + 1, and initialize all elements to 0.
  • Iterate through the array and for each element increment the corresponding index in the Hash array.

Complexity:

  • Time Complexity: We are finding the maximum element by iterating through the whole array O(N). Then we add the array values to their corresponding indexes into the hash array which takes O(N) time. Total time complexity comes as 2*O(N) -> O(N)
  • Space Complexity: The hash array is created which is of size max_element+1. If max_element is M, then this array requires O(M) space.