Sort by

recency

|

2465 Discussions

|

  • + 0 comments

    here's My solution:

    def arrayManipulation(n, queries):
        arr = [0] * (n )    
        
        for i in queries:
            l=i[0]-1 #made it 0th index
            r=i[1] #let it be 1 indexed
            arr[l]+=i[2]
            if r<n: #so that r doesn't cause out of index error
                arr[r]-=i[2]
                
        
        # Compute prefix sum and track the maximum value
        max_value = 0
        current_sum = 0
        for i in arr:
            current_sum += i
            if current_sum > max_value:
                max_value = current_sum
        
        return max_value
    
  • + 0 comments

    Data structures and arrays are fundamental concepts in computer science, forming the backbone of efficient data storage and manipulation. betbook250 register

  • + 0 comments

    public static long arrayManipulation(int n, List> queries) { // Write your code here // Use an array to store changes at boundaries long[] arr = new long[n + 2];

        // Process each query using the difference array technique
        for (List<Integer> query : queries) {
            int start = query.get(0);
            int end = query.get(1);
            int value = query.get(2);
    
            arr[start] += value;  // Add value at start index
            arr[end + 1] -= value; // Subtract value after the end index
        }
    
        // Find the maximum value by applying prefix sum
        long maxValue = 0;
        long currentSum = 0;
    
        for (int i = 1; i <= n; i++) {
            currentSum += arr[i];
            maxValue = Math.max(maxValue, currentSum);
        }
    
        return maxValue;
    }
    
  • + 2 comments

    You can look at the queries as histograms so you've got a bunch of histograms and you want to combine them. Basically you don't want overlapping queries.

    A way to do this is to consider each index in the queries as a level transition. Doesn't matter if it's at the query start index or the end index. You can just make tuples of...( transition_index, level_change) A starting query index has positive level_change. An ending query index has a neg. level_change. Just track the sum level as you go

    • + 0 comments

      def flatten_queries(queries): my_tups = [] for q in queries: my_tups.append( (q[0], q[2]) ) my_tups.append( (q[1]+1, q[2]*-1) )

      sorted_tuples = sorted(my_tups, key=lambda x: (x[0],x[1]))
      print(f'sorted_tuples: {sorted_tuples}')
      
      # {start: [end, acc], ...}
      f_query = [ [sorted_tuples[0][0], None, sorted_tuples[0][1]] ]
      max_arr = [sorted_tuples[0][1]]
      amt = sorted_tuples[0][1]
      
      for pt, acc in sorted_tuples[1:-1]:
          f_query[-1][1] = pt
      
          amt += acc
          tmp = [pt, None, amt]
          f_query.append(tmp)
          max_arr.append(f_query[-1][2])
      
      f_query[-1][1] = sorted_tuples[-1][0]
      
      print(f'f_query: {f_query}')
      print(f'max is: {max(max_arr)}')
      return max(max_arr)
      
  • + 0 comments
    It passes 9 test cases out of 16 test cases and remaining 7 test cases it says time limit exceeded......What to do??
    
    def arrayManipulation(n, q):
        # Write your code here
        temp=[]
        for i in range(0,n):
            temp.append(0)
        for j in range(len(q)):
            a,b,k=q[j][0],q[j][1],q[j][2]
            for z in range(a-1,b):
                temp[z]=temp[z]+k
        return max(temp)
    		
    	
    		UPDATED USED PREFIX SUM AND DIFFERENCE ARRAY TO OPTIMIZE THE CODE
    		
    		def arrayManipulation(n, q):
        # Write your code here
        temp=[]
        for i in range(0,n):
            temp.append(0)
        for j in range(len(q)):
            a,b,k=q[j][0],q[j][1],q[j][2]
            temp[a-1]=temp[a-1]+k
            if b<n:   # if b<len(temp):
                temp[b]=temp[b]-k
        sum=0
        maxi=0
        for z in range(len(temp)):
            sum=sum+temp[z]
            maxi=max(sum,maxi)
        return maxi