846. Hand of Straights | Leetcode POTD 6 June 2024 | Java | Heap | Striver's A to Z DSA Sheet
Vložit
- čas přidán 5. 09. 2024
- To solve this problem, we can leverage our understanding of priority queues, regular queues, and stacks. The core idea of the algorithm is to consistently select the cards with the smallest values and then proceed to the next smallest cards, all while preserving the current sequence using a queue or stack.
Here's how the algorithm works in detail:
1. **Initialization**: Begin by arranging the cards in a priority queue. This helps in always picking the card with the minimum value efficiently.
2. **Selection Process**: Continuously pick the smallest card from the priority queue.
3. **Sequence Preservation**: Use a regular queue or stack to maintain the sequence of cards.
4. **Grouping**: Always look for a group of k consecutive cards.
5. **Validation**: If the cards in the selected group are not consecutive, return false.
By following these steps, we ensure that we can systematically and efficiently determine if the cards can be grouped into sets of k consecutive cards. If at any point, the sequence is broken, the function will immediately identify this and return false.
This approach leverages the strengths of different data structures to manage and maintain order, making it both intuitive and efficient for solving this type of problem.
Link to the problem: leetcode.com/p...
Other problems for practice:
• 992. Subarrays with K ...
• 1423. Maximum Points Y...
• Max Consecutive Ones I...
• Sum of Subarray Ranges...
• Sum of Subarray Minimu...
• Expression Add operato...
• Word Search | Leetcode...
• Letter combinations of...
crisp and clear explaination
Thankyou!
I appreciate this content. Radhe radhe
very good explanation
Nice and simple approach. Use a Heap, Hash-map and a Queue. Use these to populate the bucket of cards. Good one. You can code the intuition even when your are inebriated or under the influence of THC.
Thanks ma'am :)🙏 (rnt= 35ms, bts = 47.39%)
Mam aap great ho🎉😮kya hi pyara explanation tha😅
Heeey
not an optimal solution
here is an optimal with nlogn tc and n sc
class Solution {
public static boolean isNStraightHand(int[] hand, int groupSize) {
if (hand.length % groupSize == 1) {
return false;
}
PriorityQueue pq = new PriorityQueue((p1, p2) -> {
if (p1.element == p2.element) {
return Integer.compare(p1.cnt, p2.cnt);
}
return Integer.compare(p1.element, p2.element);
});
Arrays.sort(hand);
for (int tmp : hand) {
if (pq.isEmpty()) {
pq.add(new Pair(tmp, 1));
if (pq.peek().cnt == groupSize) pq.poll();
continue;
}
if (tmp - 1 == pq.peek().element) {
Pair pair = pq.poll();
pair.element = tmp;
pair.cnt++;
if (pair.cnt < groupSize) {
pq.add(pair);
}
} else {
pq.add(new Pair (tmp, 1));
}
}
if (pq.isEmpty()) {
return true;
}
return false;
}
static class Pair {
int element;
int cnt;
public Pair (int element, int cnt) {
this.element = element;
this.cnt = cnt;
}
}
}
cpp me bhi code de diya karyie please.
Bhai gpt ka use kr liya kr
CPP Implementation
struct MyComp
{
bool operator()(pair &t1, pair &t2)
{
return t1.first > t2.first;
}
};
class Solution {
public:
bool isNStraightHand(vector& hand, int groupSize) {
if(hand.size() % groupSize != 0) return false;
unordered_map mpp;
priority_queue pq;
for(auto it : hand)
{
mpp[it]++;
}
for(auto it : mpp)
{
pq.push({it.first, it.second});
}
while(!pq.empty())
{
auto top = pq.top();
pq.pop();
top.second--;
vector temp;
for(int i=1; i < groupSize; i++)
{
if(!pq.empty() && top.first + i == pq.top().first)
{
auto tp = pq.top();
pq.pop();
tp.second--;
if(tp.second > 0)
{
temp.push_back(tp);
}
}
else
{
return false;
}
}
for(auto it : temp)
{
pq.push(it);
}
if(top.second > 0)
{
pq.push(top);
}
}
return true;
}
};
AlgorithmHQ >> takeUForward !
kuch bhi 😅😅ye khud usi chanel se padti hogi🤣🤣
@@akworld2739 Doesn't matter.