K-th Smallest in Lexicographical Order | Super Detailed | Dry Run | Leetcode 440 | codestorywithMIK
523Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 7th Video of our Playlist "Recursion : Popular Interview Problems" by codestorywithMIK
Related Similar Medium Level Version of This Problem - • Lexicographical Numbers | Simple DFS ...
In this video we will try to solve a good problem : K-th Smallest in Lexicographical Order | Super Detailed | Dry Run | Leetcode 440 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : K-th Smallest in Lexicographical Order | Super Detailed | Dry Run | Leetcode 440 | codestorywithMIK
Company Tags : will update later
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/k-th-sm...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
We will see an optimal solution to find the k-th smallest number in lexicographical order from 1 to n. The idea is based on prefix trees (tries) and counting the lexicographical order of numbers.
Key Concepts:
Prefix Tree Concept: Numbers in lexicographical order can be visualized as a prefix tree where the root represents 1, 2, ..., 9. From each node, its children represent numbers that share the same prefix. For example, from node 1, the children represent 10, 11, 12, ..., 19.
Counting the Numbers under a Prefix: For each number (starting with curr), we need to count how many numbers share that prefix in the range from 1 to n. This is done using the countNumbers function. It computes how many numbers exist between the current prefix curr and the next prefix next by expanding the prefix range (e.g., 1 to 10 to 100).
Skipping Prefixes: If the count of numbers with the current prefix is less than or equal to k, it means the desired number is beyond this prefix subtree. So, we skip the whole prefix subtree by incrementing curr. If the count is greater than k, the desired number lies within this subtree, so we move deeper by multiplying curr by 10 (moving to the next level in the tree).
Iteration Until k Reaches Zero: This process repeats until we narrow down to the k-th smallest number. The value of k decreases as we skip prefixes, and the algorithm stops once k reaches 0.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik