Why should you practice coding problems?
Want a job at companies like Google, Facebook, Amazon, and more? Software engineering interviews mainly consist of data structures and algorithm problems.
You need to do a lot of these problems in order to succeed in these interviews. Below I’ll be going through an approach to a popular problem: Array Partition I.
Please consider subscribing on YouTube by clicking here if you find this information useful!
Problem Statement & Approaach
The problem statement is:
“Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes the sum of min(ai, bi) for all i from 1 to n as large as possible.”
This basically says group an array of integers into pairs, take the minimum of those pairs, add them up. You should produce the largest sum possible, with these constraints. Below I have a full overview of the problem, with a solution.
If you want a better sense visually of how this is done, check out my in-depth explanation on YouTube below.
LeetCode: Array Partition I (Overview and Solution)
We want to make as many large numbers the minimums, and the general approach is to first sort the array. Once sorted, you’ll notice that we have forced as many large numbers to be the smallest of each pair.
Since we first need to sort the array, then loop through again, our time complexity is O(n log n) time (sorting is O(n log n), looping is O(n), so the sorting overpowers the second loop. Our space complexity is O(1), since we’re sorting in place, and creating a final sum in the end.
Conclusion
If you found this video useful, please consider subscribing to my YouTube Channel! I talk about software & technology, overviews of coding problems, and landing jobs in tech!
Also, make sure to check out our Discord community! 4700+ members, mentorship, discussion, and resources for learning to code!
On TikTok, I mainly do quick coding, tech and productivity tips. Check them out here: TikTok
Here are the social platforms where we can connect:
YouTube
Discord
TikTok
Twitter
LinkedIn
Thanks for reading, and feel free to DM any questions!
Top comments (0)