Let Code Day53 Starting from Zero "1365. How Many Numbers Are Smaller Than the Current Number"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

Apparently, many engineers take measures on the site called LetCode.

It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.

I wrote it in a big way, but I have no plans to have such an interview at the moment.

However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

I'm solving it with Python3.

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day52 starting from zero "1351. Count Negative Numbers in a Sorted Matrix"

Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

problem

1365. How Many Numbers Are Smaller Than the Current Number

The difficulty level is Easy. I will write it because it was a good problem.

The problem is given the array nums. The problem is to design an algorithm that leads each element in those arrays more times than the other elements. It's difficult in Japanese, so let's see an example.

Input: nums = [8,1,2,2,3] Output: [4,0,1,1,3] Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). For nums[1]=1 does not exist any smaller number than it. For nums[2]=2 there exist one smaller number than it (1). For nums[3]=2 there exist one smaller number than it (1). For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Input: nums = [6,5,4,8] Output: [2,1,0,3]

Input: nums = [7,7,7,7] Output: [0,0,0,0]

solution

A simple idea is to associate it with the index.

It sorts nums, retrieves it with the original index in the for statement, and adds it to the array.

For example, if nums = [6,5,4,8] in the example The result of sorting is num = [4,5,6,8]. If you think about that element in the index, you can see it naturally. For num = [4,5,6,8], the index will be [0,1,2,3]. Replacing this in the order nums gives[2,1,0,3], which matches the example.

If you write this flow in Python, it will look like this.

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        ans = []
        num = sorted(nums)
        for i in range(len(nums)):
            ans.append(num.index(nums[i]))
        return ans
# Runtime: 92 ms, faster than 55.84% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.
# Memory Usage: 13.8 MB, less than 79.58% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.

If you write it more concisely, you can also write as follows.

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        sorted_nums = sorted(nums)
        return [sorted_nums.index(num) for num in nums]
# Runtime: 100 ms, faster than 54.35% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.
# Memory Usage: 13.9 MB, less than 41.13% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.

There are some ways of thinking, but I thought this way of thinking was smarter. It's a good problem that you can solve smartly with a little twist, rather than thinking honestly.

So that's it for this time. Thank you for your hard work.

Recommended Posts

Let Code Day53 Starting from Zero "1365. How Many Numbers Are Smaller Than the Current Number"
Let Code Day14 starting from zero "136. Single Number"
Let Code Day 42 "2. Add Two Numbers" Starting from Zero
Let Code Day10 Starting from Zero "1431. Kids With the Greatest Number of Candies"
Let Code Day87 Starting from Zero "1512. Number of Good Pairs"
Let Code Day72 Starting from Zero "1498. Number of Subsequences That Satisfy the Given Sum Condition"
Let Code Day58 Starting from Zero "20. Valid Parentheses"
Let Code Day16 Starting from Zero "344. Reverse String"
Let Code Day89 "62. Unique Paths" Starting from Zero
Let Code Day 55 "22. Generate Parentheses" Starting from Zero
Let Code Day18 starting from zero "53. Maximum Subarray"
Let Code Day 13 "338. Counting Bits" Starting from Zero
Let Code Day71 Starting from Zero "1496. Path Crossing"
Let Code Day 61 "7. Reverse Integer" starting from zero
Let Code Day 82 "392. Is Subsequence" Starting from Zero
Let Code Day51 Starting from Zero "647. Palindromic Substrings"
Let Code Day 50 "739. Daily Temperatures" Starting from Zero
Let Code Day 15 "283. Move Zeroes" starting from zero
Let Code Day6 Starting from Zero "1342. Number of Steps to Reduce a Number to Zero"
Let Code Day52 Starting from Zero "1351. Count Negative Numbers in a Sorted Matrix"
Let Code Day73 Starting from Zero "1491. Average Salary Excluding the Minimum and Maximum Salary"
Let Code Day 43 "5. Longest Palindromic Substring" Starting from Zero
Let Code Day74 starting from zero "12. Integer to Roman"
Let Code Day1 Starting from Zero "1389. Create Target Array in the Given Order"
Let Code Day21 Starting from Zero "448. Find All Numbers Disappeared in an Array"
Let Code Day57 Starting from Zero "35. Search Insert Position"
Let Code Day47 Starting from Zero "14. Longest Common Prefix"
Let Code Day78 Starting from Zero "206. Reverse Linked List"
Let Code Day 60 starting from zero "1481. Least Number of Unique Integers after K Removals"
Let Code Day 79 "1282. Group the People Given the Group Size They Belong To" Starting from Zero
Let Code Day 84 starting from zero "142. Linked List Cycle II"
Let Code Day24 Starting from Zero "21. Merge Two Sorted Lists"
Let Code Day12 Starting from Zero "617. Merge Two Binary Trees"
Let Code Day2 Starting from Zero "1108. Defanging an IP Address"
Let Code Day70 Starting from Zero "295. Find Median from Data Stream"
Let Code Day81 "347. Top K Frequent Elements" Starting from Zero
Let Code Day48 Starting from Zero "26. Remove Duplicates from Sorted Array"
Let Code Day54 Starting from Zero "1290. Convert Binary Number in a Linked List to Integer"
Let Code Day67 Starting from Zero "1486. XOR Operation in an Array"
Let Code Day7 starting from zero "104. Maximum Depth of Binary Tree"
Let Code Day86 Starting from Zero "33. Search in Rotated Sorted Array"
Let Code Day92 Starting from Zero "4. Median of Two Sorted Arrays"
Let Code Day5 starting from zero "1266. Minimum Time Visiting All Points"
Let Code Day 35 "160. Intersection of Two Linked Lists" Starting from Zero
Let Code Day83 Starting from Zero "102. Binary Tree Level Order Traversal"
Let Code Day75 starting from scratch "15.3 Sum"
Let Code Day 29 "46. Permutations" starting from scratch
Let Code Day 40 Starting from Zero "114. Flatten Binary Tree to Linked List"
Let Code Day 91 "153. Find Minimum in Rotated Sorted Array" starting from zero
Let Code Day59 starting from zero "1221. Split a String in Balanced Strings"
Let Code Day 11 Starting from Zero "1315. Sum of Nodes with Even-Valued Grandparent"
Let Code Day 27 "101. Symmetric Tree" starting from scratch
Let Code Day 41 "394. Decode String" starting from scratch
Let Code Day 25 "70. Climbing Stairs" starting from scratch
Let Code Table of Contents Starting from Zero
Let Code Day69 starting from scratch "279. Perfect Squares"
Let Code Day 34 starting from scratch "118. Pascal's Triangle"
Let Code Day85 starting from scratch "6. ZigZag Conversion"
Let Code Day20 starting from scratch "134. Gas Station"
Let Code Day 88 "139. Word Break" starting from scratch
Let Code Day 28 "198. House Robber" starting from scratch