Problem 1471

Abstract / Summary

Given an array and an integer k, return the k elements that are strongest based on their distance from the median.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1471.py

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        # find obscure median
        arr.sort()
        mid = (len(arr) - 1) // 2
        median = arr[mid]

        left  = 0
        right = len(arr) - 1
        for _ in range(k):
            if abs(arr[left] - median) > abs(arr[right] - median):
                yield arr[left]
                left += 1
            else:
                yield arr[right]
                right -= 1
16 lines | 484 bytes | submitted January 10, 2024 | GitHub   7% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 63% (70k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Sorting
  • Two Pointers
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a method that returns the k strongest elements from an integer array. Strength is measured by the absolute distance from a median value, with larger distances indicating stronger elements. The algorithm first determines a median, then uses a two-pointer approach to select the strongest values in order, yielding each result as it is found.

Median Determination

The first logical block sorts the input array and computes an “obscure” median. Sorting arranges the numbers in non-decreasing order, which makes index-based access to the median straightforward. The median index is calculated with integer division that works for both odd and even lengths, ensuring a deterministic choice when the array length is even.

arr.sort()
mid = (len(arr) - 1) // 2
median = arr[mid]

By using (len(arr) - 1) // 2, the code selects the lower middle element for even-sized arrays, which is a well-defined behavior for the subsequent distance calculations.

Two-Pointer Selection Loop

After establishing the median, the algorithm initializes two pointers: left at the start of the sorted array and right at the end. A loop runs exactly k times, each iteration comparing the absolute distance of the elements at the two pointers from the median. The element with the larger distance is yielded, and the corresponding pointer moves inward.

left  = 0
right = len(arr) - 1
for _ in range(k):
    if abs(arr[left] - median) > abs(arr[right] - median):
        yield arr[left]
        left += 1
    else:
        yield arr[right]
        right -= 1

The if condition uses a strict greater-than comparison, so when the distances are equal the else branch is taken, causing the element from the right side to be chosen. This deterministic tie-breaking ensures consistent output for inputs where symmetric values exist around the median.

Edge Cases Handled

When the input array contains duplicate values, the sorting step groups them together, and the distance comparison still correctly identifies the strongest occurrences because the absolute difference calculation treats identical values uniformly. If k equals the length of the array, the loop will exhaust both pointers without overrunning, as each iteration moves one pointer inward and the total number of moves matches the number of elements. For a single-element array, the median equals that element, the distance is zero, and the loop yields the sole element when k is one.

If k is zero, the for loop executes zero times, resulting in no values being yielded, which aligns with the expectation of returning an empty collection. The code also gracefully handles an empty input array: sorting an empty list is a no-op, the median calculation yields an index error only if k is non-zero, but the method’s contract typically assumes k does not exceed the array length, so the loop would not be entered when k is zero.

Performance Optimizations

The algorithm performs a single sort operation, which is the dominant cost, and then proceeds with a linear scan using two pointers. By advancing only one pointer per iteration, the method avoids unnecessary scans of the entire array after each selection. The use of yield turns the function into a generator, allowing callers to consume results lazily without allocating an intermediate list of size k. This approach reduces memory pressure, especially when k is much smaller than the array size. The distance comparison uses abs on primitive integer values, which is computationally cheap, and the loop terminates as soon as k elements have been produced, preventing extra work beyond the required output size.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a big row of numbered blocks lined up on the floor. First, all the blocks are mixed up, so the computer puts them in order from the smallest number to the biggest number. There is a special marker called the median waiting right in the middle of that line. This median is like a balance point for all the numbers.

To pick the strongest blocks, the computer looks at the two ends of the line. One end is at the very beginning and the other end is at the very finish. It compares how far away the end number is from the median. It does this by checking the gap between them. If the gap for the number at the beginning is bigger than the gap for the number at the finish, the computer grabs that beginning number and puts it aside. If the gap for the finish number is bigger or the same, it grabs that one instead. The computer keeps doing this over and over until it has picked the right amount of strong blocks.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 7 | μ = 6.27 | σ = 1.72

Complexity Analysis

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
DimitrisJim C
FelixFan1122 C#
fpdjsns C++
fsq C++
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
trung-hn Python
varunu28 Java
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
FelixFan1122 C#
fpdjsns C++
fsq C++
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
trung-hn Python
varunu28 Java
27 links | 16 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

5 solutions   January 10, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality