Leetcode Problem 1600-1699

---

1658. Minimum Operations to Reduce X to Zero

---

1663. Smallest String With A Given Numeric Value 🌟🌟

---

1672. Richest Customer Wealth 🌟

O(N^2) Time and O(1) Space solution

• Use inbuilt accumulate function to get the sum of all the elements in the array

---

1675. Minimize Deviation in Array 🌟🌟🌟

Priority Queue (AC)

Set

Must Read

• [✅ C++

  Easy

  2 Approaches

  Priority Queue

  Set](https://leetcode.com/problems/minimize-deviation-in-array/discuss/1781709/C%2B%2B-oror-Easy-oror-2-Approaches-oror-Priority-Queue-oror-Set)

---

1679. Max Number of K-Sum Pairs 🌟🌟

Brute force(TLE)

• Try all possible combinations of numbers and find the maximum number of operations out of them.
• Time complexity: O(n^2)
• Space complexity: O(1)

Two pointer approach

• To optimize the brute force approach, we can use two pointer approach.
• sort the array.
• take one pointer at the start and one at the end.
• if the sum of the elements at both the pointers is less than k, then we need to increase the sum, so we will move the pointer at the start to the next element.
• if the sum of the elements at both the pointers is greater than k, then we need to decrease the sum, so we will move the pointer at the end to the previous element.
• if it is equal to k, then we will increase the count of operations and move both the pointers to the next and previous element respectively.
• repeat the process until both the pointers meet.
• Time complexity: O(nlogn)
• Space complexity: O(1)

Hashmap

• We can use a hashmap to store the frequency of each element.
• we will check for pair of elements whose sum is equal to k.(i.e.{nums[i], k - nums[i]})
• if we find such a pair, then we will increase the count of operations and decrease the frequency of both the elements by 1.
• if we don’t find such a pair, then we will increase the frequency of the element by 1.
• repeat the process until we reach the end of the array.
• Time complexity: O(n)
• Space complexity: O(n)

---

1696. Jump Game VI 🌟🌟

Recursion (TLE)

• Try whats the question asking.
• For every index try to jump 1 to k steps, and get maximum score.
• if we reach outside return nums[n-1].
• TC: O(k^n)
• SC: O(n), Recursion stack

Memoization (TLE)

• Memoize the result by storing it in memo array of INT_MIN.
• TC: O(k*n)
• SC: O(n), Memoization array

Tabulation (TLE) 🤕

• TC: O(k*n)
• SC: O(n), Memoization array

Tabulation optimization with multiset

• TC: O(n log k)
• SC: O(n)

Further optimization with dequeue

• TC: O(n)
• SC: O(n)

---