Ruby Solution


  • 0
    I

    link https://leetcode.com/problems/range-sum-query-immutable/

    As I met 307. Range Sum Query - Mutable first, I’ve got some “advanced” thoughts on RMQ after passing it. So that’s why I was stuck on this problem, Einstellung.

    At first, I made a SparseTable, which is O(NlogN) on preprocessing and O(logN) on query. Time Limit Exceed.

    # This is a sparse table calculating sum of data[i..j]
    class SparseTable
      attr_reader :data, :value
    
      def initialize(data)
        @data = data.empty? ? [0] : data
        @value = Array.new(@data.count) { Array.new(@data.count) {0} }
    
        build
      end
    
      def query(i, j)
        recur_query(i, j)
      end
    
      private
    
        # setup value, which value[i][j] represents sum of data[i..i+2**j-1]
        def build
          data.each_index do |i|
            value[i][0] = data[i]
          end
    
          j = 1
          loop do
            break if 2**j > data.count
    
            data.each_index do |i|
              left  = value[i][j-1]
              right = i+2**(j-1) > data.count - 1 ? 0 : value[i+2**(j-1)][j-1]
    
              value[i][j] = left + right
            end
    
            j += 1
          end
        end
    
        def recur_query(i, j)
          return 0 if i > j
    
          j = data.count - 1 if j > data.count - 1
    
          bin = (j-i+1).to_s(2)
          sum = 0
          pos = i
    
          bin.chars.reverse.each_with_index do |ch, k|
            next if ch == '0'
    
            sum += value[pos][k]
            pos += 2**k
          end
    
          sum
        end
    end
    

    Then, I made a bottom-up DP version, which is O(N^2) on preprocessing and O(1) on query. As I’m writing Ruby, this is still a TLE.

    # DP version with preprocessing O(N^2) and query O(1)
    class NumArray
      attr_reader :value, :nums
    
      def initialize(nums)
        @nums = nums
        @value = Array.new(nums.count) { Array.new(nums.count) {0} }
    
        nums.each_index do |i|
          @value[i][i] = nums[i]
        end
    
        gap = 1
        loop do
          break if gap > nums.count - 1
    
          nums.each_index do |i|
            break if i+gap > nums.count - 1
    
            @value[i][i+gap] = @value[i][i+gap-1] + nums[i+gap]
          end
    
          gap += 1
        end
      end
    
      def sum_range(i, j)
        j = @nums.count - 1 if j > @nums.count - 1
    
        value[i][j]
      end
    end
    

    After these stupid TLE attempts, I noticed that this is an “easy” problem and I know this should be passed by O(N) (or O(NlogN)) on preprocessing and O(1) on query. So finally, pass it by

    class NumArray
      attr_reader :nums, :sum
    
      def initialize(nums)
        @nums = nums
        @sum  = Array.new( @nums.count ) {0}
        preprocess
      end
    
      def sum_range(i, j)
        sum[j] - sum[i] + nums[i]
      end
    
      private
    
        def preprocess
          sum[0] = nums[0]
    
          nums.each_index do |i|
            next if i == 0
    
            sum[i] = sum[i-1] + nums[i]
          end
        end
    end
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.