# Problem - Leetcode

Given an integer array `nums`

and an integer `k`

, return *the* `k`

*most frequent elements*. You may return the answer in **any order**.

**Example 1:**

```
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
```

**Example 2:**

```
Input: nums = [1], k = 1
Output: [1]
```

**Constraints:**

`1 <= nums.length <= 10<sup>5</sup>`

`-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>`

`k`

is in the range`[1, the number of unique elements in the array]`

.It is

**guaranteed**that the answer is**unique**.

**Follow up:** Your algorithm's time complexity must be better than `O(n log n)`

, where n is the array's size.

# Answer-1 in Golang

```
func topKFrequent(nums []int, k int) []int {
countMap := map[int]int{}
for _, num := range nums {
if count, ok := countMap[num]; ok {
countMap[num] = count + 1
} else {
countMap[num] = 1
}
}
countSlice := make([][]int, len(nums)+1)
for num, count := range countMap {
countSlice[count] = append(countSlice[count], num)
}
res := []int{}
for i := len(countSlice) - 1; i > 0; i-- {
res = append(res, countSlice[i]...)
if len(res) == k {
return res
}
}
return res
}
```

This code defines a Go function called `topKFrequent`

takes a slice of integer `nums`

and an integer `k`

as its parameters. The goal of this function is to find the `k`

most frequent numbers from the input slice and return them in an output slice.

Here's how the code works:

`countMap := map[int]int{}`

- This initializes an empty map called
`countMap`

. The keys of this map will be the unique numbers from the input slice, and the values will be the frequency (count) of each number.

- This initializes an empty map called
Loop through

`nums`

to populate`countMap`

:The loop iterates through each number

`num`

in the input slice`nums`

.If

`num`

is already a key in`countMap`

, it increments the count by 1.If

`num`

is not a key in`countMap`

, it adds`num`

to the map with a count of 1.

`countSlice := make([][]int, len(nums)+1)`

- This creates a 2D slice called
`countSlice`

. The outer slice will store lists of numbers grouped by their frequency. The inner slices will store the actual numbers.

- This creates a 2D slice called
Loop through

`countMap`

to populate`countSlice`

:The loop iterates through each key-value pair in

`countMap`

.It appends the number (

`num`

) to the inner slice corresponding to its frequency (`count`

) in`countSlice`

.

Retrieve the

`k`

most frequent numbers:- The code initializes an empty result slice called
`res`

.

- The code initializes an empty result slice called
Iterate through

`countSlice`

in reverse order:Starting from the highest possible frequency (length of

`countSlice`

- 1), it iterates in reverse.It appends the numbers in the current frequency group to the result slice

`res`

.If the length of

`res`

becomes equal to or greater than`k`

, it means the required`k`

most frequent numbers have been found, so the function returns`res`

.

If the loop completes without finding

`k`

most frequent numbers:- If the loop completes without returning, it means the total number of unique numbers is less than
`k`

. In this case, it just returns the`res`

slice.

- If the loop completes without returning, it means the total number of unique numbers is less than

In summary, this code calculates the frequency of each number in the input slice, groups the numbers based on their frequency, and returns the `k`

most frequent numbers. The approach is based on using a frequency map and a frequency-based grouping in a 2D slice.

# Answer-2 Top Runtime in Golang

```
import (
"math"
"sort"
)
func topKFrequent(nums []int, k int) []int {
n := len(nums)
if n < 2 {
return nums
}
min, max := math.MaxInt32, math.MinInt32
for _, val := range nums {
if min > val {
min = val
}
if max < val {
max = val
}
}
numRange := max - min
//[counter, index-to-next]
allCounters := make([][2]int, numRange+2)
firstValue := nums[0]
prevValue := firstValue - min +1
diffCount := 1
allCounters[prevValue][0] = 1
allCounters[prevValue][1] = -1
for _, val := range nums[1:] {
realVal := val - min + 1
allCounters[realVal][0] += 1
if allCounters[realVal][1] == 0 {
diffCount++
allCounters[realVal][1] = prevValue
prevValue = realVal
}
}
allPairs := make([][2]int, diffCount)
//fmt.Printf("#count: %v\n", diffCount)
idx := 0
for diffCount > 0 {
val := prevValue + min - 1
allPairs[idx][0] = allCounters[prevValue][0]
allPairs[idx][1] = val
prevValue = allCounters[prevValue][1]
idx++
diffCount--
}
sort.Slice(allPairs, func(i, j int) bool {
return allPairs[i][0] > allPairs[j][0]
})
res := make([]int, k)
idx = 0
for idx < k {
res[idx] = allPairs[idx][1]
idx++
}
return res
}
```

This code defines a function `topKFrequent`

that takes an array of integers `nums`

and an integer `k`

as input and returns an array containing the top K most frequent elements in the input array. Let's break down the code step by step:

The

`import`

statements: The code imports the necessary packages`math`

and`sort`

for mathematical operations and sorting, respectively.Function

`topKFrequent`

: This function calculates the top K most frequent elements in the`nums`

array.Calculating the length of the input array: The variable

`n`

stores the length of the`nums`

array.Handling edge cases: If the length of the array is less than 2, the function returns the original array as there won't be any "top K frequent" elements.

Finding the minimum and maximum values in the array: This loop iterates through the

`nums`

array and finds the minimum (`min`

) and maximum (`max`

) values.Calculating the range of values: The variable

`numRange`

calculates the range of values in the array by subtracting the minimum from the maximum value.Initializing an array for counters and indices: The

`allCounters`

array is created to store two values for each element: its frequency count and the index of the next element with the same frequency.Initializing variables:

`firstValue`

holds the value of the first element in the array.`prevValue`

is initialized with the adjusted value of the first element based on the minimum value.`diffCount`

keeps track of the number of unique frequencies encountered.

Storing frequency and index information:

The frequency of the first element is set to 1 in

`allCounters`

.The index of the next element with the same frequency is set to -1.

Iterating through the array to count frequencies and indices:

This loop iterates through the

`nums`

array starting from the second element.It adjusts the current value based on the minimum value and stores it as

`realVal`

.The frequency count of

`realVal`

is incremented in`allCounters`

.If the index of the next element with the same frequency is 0, it means this is a new frequency. In that case,

`diffCount`

is incremented, and the index is updated.

- Creating an array of frequency-value pairs:

- An array
`allPairs`

is created to store the frequency-value pairs for the unique frequencies encountered.

- Populating the
`allPairs`

array:

This loop iterates until

`diffCount`

becomes 0.The original value is calculated by adding

`min - 1`

to the adjusted value.Frequency and value are stored in

`allPairs`

, and the next index is updated.

Sorting the pairs by frequency: The

`allPairs`

array is sorted in descending order based on frequency.Extracting the top K frequent elements:

An array

`res`

is created to store the final result.The loop extracts the top K elements from

`allPairs`

and stores their values in`res`

.

- Returning the result: The function returns the
`res`

array containing the top K frequent elements in descending order of frequency.

This code implements a more complex algorithm to solve the problem of finding the top K most frequent elements by managing indices and frequencies directly.

# Answer-3 Top Memory in Golang

```
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
type Pair struct {
fr int
sc int
}
func topKFrequent(nums []int, k int) []int {
mn, mx := nums[0], nums[0]
for _, v := range nums {
mn = min(mn, v)
mx = max(mx, v)
}
counter := make([]Pair, mx-mn+1)
shift := mn
for _, v := range nums {
counter[v-shift].fr += 1
counter[v-shift].sc = v
}
sort.Slice(counter, func(i, j int) bool {
return counter[i].fr > counter[j].fr
})
ans := make([]int, k)
for i := 0; i < k; i++ {
ans[i] = counter[i].sc
}
return ans
}
```

This code defines a function `topKFrequent`

that takes an array of integers `nums`

and an integer `k`

as input and returns an array containing the top K most frequent elements in the input array. Let's break down the code step by step:

**Function Definitions for max and min:**- Two utility functions
`max`

and`min`

are defined. They return the maximum and minimum of two integer values, respectively.

- Two utility functions
**Defining a Pair Struct:**- A custom data structure
`Pair`

is defined to hold two integer values,`fr`

(frequency) and`sc`

(score/value). This will be used to store frequency-score pairs.

- A custom data structure
**Function**`topKFrequent`

:- This function calculates the top K most frequent elements in the
`nums`

array.

- This function calculates the top K most frequent elements in the
**Finding the Minimum and Maximum Values in the Array:**The variables

`mn`

and`mx`

are initialized with the first element of the`nums`

array.A loop iterates through the

`nums`

array and updates`mn`

and`mx`

to find the minimum and maximum values.

**Creating a Counter Array:**An array named

`counter`

of type`Pair`

is created to store frequency-score pairs.The variable

`shift`

is set to`mn`

. This will be used to adjust the index in the`counter`

array so that the minimum value corresponds to index 0.

**Populating the Counter Array:**Another loop iterates through the

`nums`

array.The frequency of the element

`v`

is incremented in the`counter`

array at the index`v - shift`

. The corresponding score`v`

is also stored.

**Sorting the Counter Array:**- The
`counter`

array is sorted in descending order based on frequency. The`sort.Slice`

function is used with a custom comparison function that compares the frequencies of two`Pair`

objects.

- The
**Extracting the Top K Frequent Elements:**An array

`ans`

is created to store the final result.A loop iterates

`k`

times.The score of the

`i`

-th element in the sorted`counter`

array is assigned to the`i`

-th element of the`ans`

array.

**Returning the Result:**- The function returns the
`ans`

array containing the top K frequent elements.

- The function returns the

In summary, this code calculates the frequency of each element in the input array and stores the frequencies along with the corresponding values in a custom `Pair`

structure. Then, it sorts the pairs based on frequency and extracts the top K elements by copying their values into the result array. This approach optimizes memory usage and avoids creating a separate map to store frequencies.