educative.io

Space Optimization with 1D array?

Courses
,
#1

Can we use a 1D array for the bottom-up solution?

Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: Longest Repeating Subsequence - Grokking Dynamic Programming Patterns for Coding Interviews

#2

Hello @Vrdko93,
Yes, you are right. For LRS we can also achieve our result with a 1D array, but if we use the same bottom-up dynamic solution which is also used for LCS, a 2D array is required.
Hope this helps.