DEV Community

Cover image for Think Like Programmer: Problem Solving
Denis Rasulev
Denis Rasulev

Posted on • Edited on • Originally published at denshub.com

Think Like Programmer: Problem Solving

Always up to date version you will find on Den's Hub: https://denshub.com

Intro

In order to keep my programming skills sharp, from time to time I solve problems on the LeetCode. It's great because it's constantly evolving, it has a friendly interface, you can choose problems on topics that interest you and there's an excellent community, from which you can learn a lot.

I've always been interested to know what goes on in the programmers' heads when they solve problems. How does it really happen? Since I couldn't find any material on the subject, I decided to write about how it happened to me.

This publication on the LeetCode community forum provoked quite a response and got hundreds upvotes, so I'm sharing my experience here on the blog as well.

Task

Here is the task itself:

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order. Return the sorted array.

Example 1:

Input: nums = [1,1,2,2,2,3]

Output: [3,1,1,2,2,2]

Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

Start

Early Sunday morning, music from Spotify, hot coffee, favorite console, great mood... Task from the list of tasks "to solve later".

Let's go! Starting Python, enter initial input...

~  python3                                                                         
Python 3.9.1 (default, Feb 3 2021, 07:38:02)
[Clang 12.0.0 (clang-1200.0.32.29)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> nums = [1,1,2,2,2,6,6,4,4,5,5,3]
Enter fullscreen mode Exit fullscreen mode

Think

Ok, so I need to count frequency of each of the unique values... First idea - use Counter. This returns collection type of object:

>>> d = Counter(nums)
>>> d
Counter({2: 3, 1: 2, 6: 2, 4: 2, 5: 2, 3: 1})
>>> type(d)
<class 'collections.Counter'>
Enter fullscreen mode Exit fullscreen mode

Now I need to sort those values following the requirements in the description. Counter object has no attribute sort, and sorted will only sort values, not frequencies. Googling options, found this StackOverflow question with lots of useful answers. Reading... Let's try easier object:

>>> r = Counter(nums).most_common()
Enter fullscreen mode Exit fullscreen mode

This returns a list of tuples, where first number is value and second - its' frequency. Can I sort it in the same command? Jumping to the official documentation. Nope, not sortable in the command itself, moreover: "Elements with equal counts are ordered in the order first encountered". Ok, let's sort it directly, first by values in the decreasing order, then by frequencies in the increasing.

>>> r.sort(key = lambda x: x[0], reverse=True)
>>> r.sort(key = lambda x: x[1])
>>> r
[(3, 1), (6, 2), (5, 2), (4, 2), (1, 2), (2, 3)]
Enter fullscreen mode Exit fullscreen mode

Looks promising. Now I want to expand those tuples into a single list... Still browsing answers to the same question. Remembering that I can expand tuple and get every number from it by using this:

>>> a, b = (3, 2)
>>> a
3
>>> b
2
Enter fullscreen mode Exit fullscreen mode

so then I can repeat every value by the number of its' frequency like so:

>>> [3]*2
[3, 3]
Enter fullscreen mode Exit fullscreen mode

Aha. Now I need an empty list to combine all those tuples into a single list:

t = []
for i in r:
    a, b = i
    t.extend([a] * b)

>>> t
[3, 6, 6, 5, 5, 4, 4, 1, 1, 2, 2, 2]
Enter fullscreen mode Exit fullscreen mode

Woo-hoo! That's what I need. So the complete solution now looks like this:

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:

        r = Counter(nums).most_common()
        r.sort(key = lambda x: x[0], reverse=True)
        r.sort(key = lambda x: x[1])

        t = []
        for i in r:
            a, b = i
            t.extend([a]*b)

        return t
Enter fullscreen mode Exit fullscreen mode

Result: Runtime: 52 ms, faster than 63.30% of Python3 online submissions for Sort Array by Increasing Frequency.

Memory Usage: 14.2 MB, less than 58.20% of Python3 online submissions for Sort Array by Increasing Frequency.

Not the best, but the task is solved.

Optimize

Now it's time for another fun - can I make it one-liner or optimize the solution in any other way? This is just pampering + training + fun :)

Looking at sorting lines... Can I sort it in one go? Yes! So, first we sort by values in the reverse order (-x[0]) and then by their frequencies (x[1]) in direct order.

>>> r.sort(key = lambda x: (x[1], -x[0]))
Enter fullscreen mode Exit fullscreen mode

Basically, it's the same operation as the above but now coded in one line. Love Python :) Same logic applies to the tuple expansion part and it allows to save another line:

t = []
for i in r:
  t += ([i[0]] * i[1])
Enter fullscreen mode Exit fullscreen mode

And then I thought - if I can sort by value and its' frequency why do I need intermediate list? Can I sort the original list the same way?! Let's see...

>>> nums
[1, 1, 2, 2, 2, 6, 6, 4, 4, 5, 5, 3]
>>> r = Counter(nums)
>>> r
Counter({2: 3, 1: 2, 6: 2, 4: 2, 5: 2, 3: 1})
>>> nums.sort(key=lambda x: (r[x], -x))
>>> nums
[3, 6, 6, 5, 5, 4, 4, 1, 1, 2, 2, 2]
Enter fullscreen mode Exit fullscreen mode

Voila! That feels sooo good. But x.sort makes it in-place and I need to return an object... So, I need to change it to sorted then:

>>> result = sorted(nums, key=lambda x: (r[x], -x))
>>> result
[3, 6, 6, 5, 5, 4, 4, 1, 1, 2, 2, 2]
Enter fullscreen mode Exit fullscreen mode

Perfect. So the final variant would be:

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        r = Counter(nums)
        return sorted(nums, key=lambda x: (r[x], -x))
Enter fullscreen mode Exit fullscreen mode

And it's even faster!

Runtime: 44 ms, faster than 95.07% of Python3 online submissions for Sort Array by Increasing Frequency.

Memory Usage: 14.3 MB, less than 58.20% of Python3 online submissions for Sort Array by Increasing Frequency.

Conclusion

Solving programming tasks requires a combination of knowledge, experience, and creative problem-solving skills. By understanding the thought process and techniques used by experienced programmers, you can improve your ability to break down complex code and identify and overcome obstacles.

With practice and perseverance, anyone can become a proficient programmer and excel in their field. Remember to always stay curious and continue learning, as technology and programming languages are continually evolving.

But most importantly, have fun!

😎

Top comments (0)