C++ Educational Content Creator | 20 years of Software Engineering experience distilled into digestible daily posts
Tuesday common C++ interview problem: Longest increasing path. Given a matrix where each element has an integer value, return the length of the longest increasing path. That is a path where the value of each element is strictly larger than the previous elements in the path (only orthogonal, no diagonals). Solve it yourself: https://lnkd.in/evF35Z_w Solution: https://lnkd.in/euf6SJdE #cpp #cplusplus #coding #programming #dailybiteofcpp
I couldn't come up with something simpler. - Two extra data structures: a map of longest paths from each coordinate, and a queue to walk the matrix of values starting from the smallest ones. - Loop until the queue is empty. - In each iteration, get the next smallest value, remove it from the queue, check possible movements (it's feasible and it's an increasing path), update the distance map, and move. https://compiler-explorer.com/z/zsnbx9W31
Here is my solution using dynamic programming! https://compiler-explorer.com/z/sY5e33xfe I tried to keep it short and readable. Any feedback is welcome :)
Air France-KLM•2K followers
3yThank you for sharing these cool puzzles every time