Text Justification Algorithm (LeetCode)
Here is a step by step explanation of a LeetCode hard problem called "Text Justification". This problem is extremely popular in technical interviews and is asked at Google, Intuit, Indeed, LinkedIn, Coursera, Pinterest, Uber, Snapchat, Amazon, and Twilio.
To solve this problem, there are two different approaches: dynamic programming OR greedy. In this video explanation, I am going to go over the greedy approach. This problem is very difficult and is in the top 50 lowest acceptance rates out of all 1500 LeetCode problems on the platform sitting at about 27 percent.
The greedy approach involves having two pointers "i" and "j". We move our "j" pointer forward until we get to a point where the words in the line go over our "maxWidth" parameter. Once that occurs, we now know all of the words that are going to be inside of the line.
Next, we will count the number of words we have in the line. If we have a single word OR we are on the last line, then we will be left justifying the line, otherwise we middle justify. To left justify a line, we take the difference between the total amount of word characters we have and our "maxWidth" and this will tell us how many spaces there needs to be inside of the line.
There should only be a single space between each word, but the last word will have the rest of the unused spaces to the very right of it, causing the line to left justify properly. In order to middle justify, we take the the number of spaces needed and the number of sections of spaces required. To get the section number, we do "j" - "i" - 1. Then divide our spaces with the section number which gives us a number to evenly distribute the spaces in between each word in the line. If we have extra spaces, the spaces will be added to the left-most words from left to right.
The time and space complexity of our solution is going to be O(lines * maxWidth). We must iterate, for each potential line, to the "maxWidth" since the spaces will be repeated. Under the hood, the "repeat" function is just running a for loop duplicating the character.
DISCORD CHANNEL
----------------------------------------------------------------------------------------------------------------
►Support me on Patreon: https://www.patreon.com/michaelmuinos
Join the Discord channel by becoming a supporter on my Patreon!
In this Discord channel, you will be able to...
1. Contact me directly for interview prep advice, tech questions, project ideas, etc.
2. Discuss interview experiences with other members
3. Discuss technical questions with other members
4. Find mock interview partners & more!
SOCIAL
-------------------------------------------------------------------------------------------
►Follow me on Twitter: https://twitter.com/MichaelMuinos
►Follow me on Github: https://github.com/MichaelMuinos
Видео Text Justification Algorithm (LeetCode) канала Michael Muinos
To solve this problem, there are two different approaches: dynamic programming OR greedy. In this video explanation, I am going to go over the greedy approach. This problem is very difficult and is in the top 50 lowest acceptance rates out of all 1500 LeetCode problems on the platform sitting at about 27 percent.
The greedy approach involves having two pointers "i" and "j". We move our "j" pointer forward until we get to a point where the words in the line go over our "maxWidth" parameter. Once that occurs, we now know all of the words that are going to be inside of the line.
Next, we will count the number of words we have in the line. If we have a single word OR we are on the last line, then we will be left justifying the line, otherwise we middle justify. To left justify a line, we take the difference between the total amount of word characters we have and our "maxWidth" and this will tell us how many spaces there needs to be inside of the line.
There should only be a single space between each word, but the last word will have the rest of the unused spaces to the very right of it, causing the line to left justify properly. In order to middle justify, we take the the number of spaces needed and the number of sections of spaces required. To get the section number, we do "j" - "i" - 1. Then divide our spaces with the section number which gives us a number to evenly distribute the spaces in between each word in the line. If we have extra spaces, the spaces will be added to the left-most words from left to right.
The time and space complexity of our solution is going to be O(lines * maxWidth). We must iterate, for each potential line, to the "maxWidth" since the spaces will be repeated. Under the hood, the "repeat" function is just running a for loop duplicating the character.
DISCORD CHANNEL
----------------------------------------------------------------------------------------------------------------
►Support me on Patreon: https://www.patreon.com/michaelmuinos
Join the Discord channel by becoming a supporter on my Patreon!
In this Discord channel, you will be able to...
1. Contact me directly for interview prep advice, tech questions, project ideas, etc.
2. Discuss interview experiences with other members
3. Discuss technical questions with other members
4. Find mock interview partners & more!
SOCIAL
-------------------------------------------------------------------------------------------
►Follow me on Twitter: https://twitter.com/MichaelMuinos
►Follow me on Github: https://github.com/MichaelMuinos
Видео Text Justification Algorithm (LeetCode) канала Michael Muinos
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Text Justification Dynamic ProgrammingCoding Interview Prep | 3 MUST KNOW Graph Problem TipsStep by step guide to solve text justification problem using dynamic programmingTrie Data Structure Implementation (LeetCode)How To Solve Amazon's Hanging Cable Interview QuestionMinimum Window Substring | Sliding Window | LeetCodeBinary Search : Median of two sorted arrays of different sizes.AMAZON CODING INTERVIEW QUESTION - COIN CHANGE (LeetCode)20. Dynamic Programming II: Text Justification, BlackjackEMPLOYEE FREE TIME (Leetcode) - Code & WhiteboardBoyer Moore Majority Vote AlgorithmLeetCode 68. Text Justification Explanation and SolutionWord Ladder | Breadth First Search (LeetCode)Ep.1: Depth-First Search - LeetCode Problems That Got Me HiredMinimum edit distance | Dynamic programming | BacktrackingGraph Coding Question - All Paths From Source To Target (LeetCode)Regular Expression Matching - Dynamic Programming Top-Down Memoization - Leetcode 10Leetcode 843(Hard) Guess the Word: Simple C++ Solution & Mathematical ExplanationSelf Taught Programmers... Listen Up.Maximal Square - Top Down Memoization - Leetcode 221