Press "Enter" to skip to content

Posts tagged as “freq”

花花酱 LeetCode 2404. Most Frequent Even Element

By zxi on September 11, 2022

Given an integer array nums, return the most frequent even element.

If there is a tie, return the smallest one. If there is no such element, return -1.

Example 1:

Input: nums = [0,1,2,2,4,4,1]
Output: 2
Explanation:
The even elements are 0, 2, and 4. Of these, 2 and 4 appear the most.
We return the smallest one, which is 2.

Example 2:

Input: nums = [4,4,4,9,2,4]
Output: 4
Explanation: 4 is the even element appears the most.

Example 3:

Input: nums = [29,47,21,41,13,37,25,7]
Output: -1
Explanation: There is no even element.

Constraints:

  • 1 <= nums.length <= 2000
  • 0 <= nums[i] <= 105

Solution: Hashtable

Use a hashtable to store the frequency of even numbers.

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 1394. Find Lucky Integer in an Array

By zxi on March 28, 2020

Given an array of integers arr, a lucky integer is an integer which has a frequency in the array equal to its value.

Return a lucky integer in the array. If there are multiple lucky integers return the largest of them. If there is no lucky integer return -1.

Example 1:

Input: arr = [2,2,3,4]
Output: 2
Explanation: The only lucky number in the array is 2 because frequency[2] == 2.

Example 2:

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

Example 3:

Input: arr = [2,2,2,3,3]
Output: -1
Explanation: There are no lucky numbers in the array.

Example 4:

Input: arr = [5]
Output: -1

Example 5:

Input: arr = [7,7,7,7,7,7,7]
Output: 7

Constraints:

  • 1 <= arr.length <= 500
  • 1 <= arr[i] <= 500

Solution: Hashtable

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 895. Maximum Frequency Stack

By zxi on August 26, 2018

Problem

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

  • push(int x), which pushes an integer x onto the stack.
  • pop(), which removes and returns the most frequent element in the stack.
    • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

Input: 
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

  • Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
  • It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
  • The total number of FreqStack.push calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

 

Solution 1: Buckets

We have n  stacks. The i-th stack has the of elements with freq i when pushed.

We keep tracking the freq of each element.

push(x): stacks[++freq(x)].push(x)  # inc x’s freq and push it onto freq-th stack

pop(): x = stacks[max_freq].pop(), –freq(x); # pop element x from the max_freq stack and dec it’s freq.

Time complexity: O(1) push / pop

Space complexity: O(n)

C++

Solution2: Priority Queue

Use a max heap with key: (freq, seq), the max freq and closest to the top of stack element will be extracted first.

Time complexity: O(logn)

Space complexity: O(n)

C++

Related Problems