We are given an elevation map, heights[i] representing the height of the terrain at that index.  The width at each index is 1.  After V units of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index.  Then, it flows according to the following rules:
If the droplet would eventually fall by moving left, then move left.
Otherwise, if the droplet would eventually fall by moving right, then move right.
Otherwise, rise at it's current position.
Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction.
Also, "level" means the height of the terrain plus any water in that column.

We can assume there's infinitely high terrain on the two sides out of bounds of the array.  Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.


Example 1:

Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
Output: [2,2,2,3,2,2,2]
Explanation:
#       #
#       #
##  # ###
#########
 0123456    


Example 2:

Input: heights = [1,2,3,4], V = 2, K = 2
Output: [2,3,3,4]
Explanation:
The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.



Example 3:

Input: heights = [3,1,3], V = 5, K = 1
Output: [4,4,4]



Note:
heights will have length in [1, 100] and contain integers in [0, 99].
V will be in range [0, 2000].
K will be in range [0, heights.length - 1].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: class Solution:
    def pourWater(self, heights: List[int], V: int, K: int) -> List[int]:
        

Solutions:
class Solution:

	def reachNumber(self, target):
		t = abs(target)
		n = math.floor(math.sqrt(2 * t))
		while True:
			to_minus = (n + 1) * n / 2 - t
			if to_minus >= 0:
				if to_minus % 2 == 0:
					return int(n)
			n += 1


class Solution:

	def reachNumber(self, target):
		target = abs(target)
		n = math.ceil(((1 + 8 * target) ** 0.5 - 1) / 2)
		if target % 2 > 0:
			if n % 4 == 1 or n % 4 == 2:
				return n
			elif n % 4 == 3:
				return n + 2
			else:
				return n + 1
		elif n % 4 == 3 or n % 4 == 0:
			return n
		elif n % 4 == 1:
			return n + 2
		else:
			return n + 1


class Solution:

	def reachNumber(self, target):
		target = abs(target)

		def binary_search(lo, hi):
			if lo >= hi:
				return lo
			mi = lo + (hi - lo) // 2
			t = mi * (mi + 1) // 2
			if t == target:
				return mi
			elif t < target:
				return binary_search(mi + 1, hi)
			else:
				return binary_search(lo, mi)
		res = binary_search(0, target)
		if target % 2 == 0 and 1 <= res % 4 <= 2:
			return res + 3 - res % 4
		elif target % 2 == 1 and (res % 4 == 3 or res % 4 == 0):
			return res + 4 - (res - 1) % 4
		else:
			return res


class Solution:

	def reachNumber(self, t):
		t = abs(t)
		(lo, hi) = (1, t)
		while lo < hi:
			m = (lo + hi) // 2
			val = m * (m + 1) // 2
			if val < t:
				lo = m + 1
			else:
				hi = m
		sm = lo * (lo + 1) // 2
		ans = lo
		while (sm - t) % 2 != 0:
			ans += 1
			sm += ans
		return ans


class Solution:

	def reachNumber(self, target):
		target = abs(target)
		s = 0
		for i in range(target + 1):
			s += i
			if s >= target:
				break
		if s - target & 1:
			if i + 1 & 1:
				return i + 1
			else:
				return i + 2
		else:
			return i