educative.io

Educative

FYI, O(n) time and O(1) space DP and Greedy solution available

There are simpler linear time solution available done with DP or Greedy.


Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5633779737559040
Lesson: https://www.educative.io/collection/page/5668639101419520/5633779737559040/5643365030821888

Hello @Allan1,

Yes, you are right that the solution to this problem is doable in O(n) time and O(1) space, but as this course is for beginners, the most important thing is to learn problem-solving without concerning about the time and space complexity. Although upon your suggestion, we will add the optimized solutions to these problems soon.

I hope I have answered your query; please let me know if you still have any confusion.

Thank You :blush: