leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

solving-questionsV3.dart (1216B)

      1 //This is a constant time solution that moves from right to left.
      2 //each time it moves it figures out where the next question it would answer is
      3 //then based on that it uses the points associated with that place to continue moving to the left
      4 //thus building upon previous calculations
      5 //Runtime: 584ms Beats: 100%
      6 //Memory: 227.2MB Beats: 100%
      7 class Solution {
      8 int mostPoints(List<List<int>> questions) {
      9         int max = 0;
     10         List<int> current_val = [];
     11         for(int i = 0 ; i < questions.length ; ++i){
     12             current_val.add(0);
     13         }
     14         for(int i = questions.length - 1; i >= 0; --i){
     15             if(current_val.length > questions[i][1] + i + 1){
     16                 int new_val = questions[i][0] + current_val[questions[i][1] + i + 1];
     17                 if(new_val > max){
     18                     max = new_val;
     19                     current_val[i] = max;
     20                 }
     21                 else{
     22                     current_val[i] = current_val[i + 1];
     23                 }
     24             }
     25             else{
     26                 if(questions[i][0] > max){
     27                     max = questions[i][0];
     28                 }
     29                 current_val[i] = max;
     30             }
     31         }
     32         return max;
     33     }
     34 
     35 }