DEV Community

Cover image for Understanding K Element Patterns in LeetCode: The Basics (Part 1)
Shavon Harris
Shavon Harris

Posted on

Understanding K Element Patterns in LeetCode: The Basics (Part 1)

I finally understand! The best way to learn LeetCode is not by grinding through problem after problem, sometimes taking a whole hour to solve them inefficiently. The key to mastering LeetCode is studying patterns. Let's study a common one!

Interviewers love asking about finding, maintaining, or manipulating K elements in a string or array. At first, I thought each problem was totally different, but then I started seeing the connections. Let me show you what I mean with two problems that really helped me understand this pattern.

Problem 1: Find Subsequence of Length K with the Largest Sum

This is technically an 'easy' level question (only asked by one company), but, it teaches you so much about how to think about these k-element problems!

What They're Asking

You get an array of numbers and a value k, and you need to find k numbers from the array that add up to the biggest possible sum. BUT (and this is the part that tripped me up at first), you have to keep the numbers in their original order!

Example:

Image description

Oh! this one is trickier:

Image description

Ok I Get It

At first, I thought "just grab the k biggest numbers, done!" But nope - that order requirement changes everything. Here's what finally clicked:

  1. We need to remember where each number came from, right? So I thought, "I should pair every number with it's position?"

Image description

  1. Then we can sort these pairs by the values (that's the first number in each pair), but we're keeping track of where they came from (that's the second number)!

Image description

  1. Now the cool part - we only need k of these, so grab the first k pairs and just keep their positions:

Image description

  1. Finally, walk through the original array and only keep numbers whose positions are in our Set:

Image description

Here's The Code

Image description

2: Kth Largest Element in a Stream

Ok, so this one's also labeled 'easy' (asked by five companies), but this one was more confusing to me than any of the more difficult Kth element problems.

What They're Asking

Imagine you're working at a university and students keep submitting test scores. Your job is to always know the kth highest score at any time. New scores keep coming in, and you need to keep track.

They give you k and some initial scores, then they keep throwing new scores at you and want to know the kth highest each time. Let's look at an example:

Image description

Ok, I Think I Get It

At first, I kept trying to sort the entire array every time a new score came in but I know that sorting can be inefficient. Then I thought why am I keeping track of all the scores when I only care about the top k?

Here's how I broke it down:

  1. First, sort the initial scores and only keep the top k:

Image description

  1. Now when a new score comes in:

If it's smaller than our kth highest (first number), ignore it
If it's bigger, it belongs in our list somewhere

Here's what's happening with each add:

Image description

The Code

Image description

Why These Two Problems Are Connected

Both problems taught me something super important about handling k elements:

  • First problem: Sometimes you need to track where elements came from
  • Second problem: Sometimes you only need to keep k elements around

These k-element problems are all about being clever with what information you keep and what you throw away.
Next time we'll look at two more k-element problems that build on these idea. I hope at the end you see a pattern and these types of problems seem less scary!

Sentry blog image

How I fixed 20 seconds of lag for every user in just 20 minutes.

Our AI agent was running 10-20 seconds slower than it should, impacting both our own developers and our early adopters. See how I used Sentry Profiling to fix it in record time.

Read more

Top comments (0)

nextjs tutorial video

Youtube Tutorial Series πŸ“Ί

So you built a Next.js app, but you need a clear view of the entire operation flow to be able to identify performance bottlenecks before you launch. But how do you get started? Get the essentials on tracing for Next.js from @nikolovlazar in this video series πŸ‘€

Watch the Youtube series

πŸ‘‹ Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay