Problem: Flood Fill Algorithm

*Difficulty: Easy

Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is to replace color of the given pixel and all adjacent same colored pixels with the given color K.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains Two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix. Then in the next line are three values x, y and K.

Output:
For each test case print the space separated values of the new matrix.

Constraints:
1<=T<=10
1<=M[][]<=100

Example:
Input:

2
3 4
0 1 1 0 1 1 1 1 0 1 2 3
0 1 5
2 2
1 1 1 1
0 1 8

Output:
0 5 5 0 5 5 5 5 0 5 2 3
8 8 8 8

Implementation: Python 2.7

def floodFill(rootColor, visited, screen, replaceColor, x, y):
# set color of x,y on the screen
screen[x][y] = replaceColor
# mark them as visited
visited.append((x, y))
# get all 4 directions
# first I make a mistake, I get all 8 directions
# but in the end, it's wrong
all_directions = [(x-1, y), (x, y+1),
(x+1, y), (x, y-1)]
# filter those 4 directions
# only get which one is in screen, not yet visited and has rootColor
all_directions = filter(lambda coor: isInScreen(coor[0], coor[1], screen) and not (coor[0], coor[1]) in visited and screen[coor[0]][coor[1]] == rootColor , all_directions)
# recursive call for those all directions
for (next_x,next_y) in all_directions:
floodFill(rootColor, visited, screen, replaceColor, next_x, next_y)

# check if (x, y) is in screen (not out of bound)
def isInScreen(x, y, screen):
return x >= 0 and x < len(screen) and y >= 0 and y < len(screen[0])

def printScreen(screen):
for row in screen:
for col in row:
print col,
print

def main():
t = input()
for _ in range(t):
n, m = map(int, raw_input().strip().split())
arr = map(int, raw_input().strip().split())
x, y, replaceColor = map(int, raw_input().strip().split())
screen, visited = [], []
# convert list-like array to matrix (actually is a list of list)
for i in range(0, len(arr), m):
screen.append(arr[i:i+m])
rootColor = screen[x][y]
floodFill(rootColor, visited, screen, replaceColor, x, y)
printScreen(screen)

if __name__ == '__main__':
main()

Problem: Sum of All Subarrays

*Difficulty: Medium

Given an array A with N elements , you need to find the sum all sub arrays of array A. Since the sum could be very large print the sum modulo (10^9+7).

Input :
The first line contains integer T, denoting number of test cases. The first line of each test case contains an integer N, denoting the number of elements.The second line of each test case contains N space separated integers denoting values of the array A.
Output :
Print the answer of each test case in a new line.

Constraints :
1<=T<=10
1<=N<=10^5

Example
Input :

2
3
1 2 3
2
1 3

Output :
20
8

*Approach 1:

Generate all sub arrays
This is O(n^3) complexity solution

Code: Python 2.7

def sum_all_sub_arrs(arr):
if len(arr) == 1:
return arr[0]
elif len(arr) == 2:
return arr[0] + arr[1] + sum(arr)
elif len(arr) == 3:
return sum(arr)*2 + arr[0] + arr[1] + arr[1] + arr[2]
else:
sum_all = 0
for i in range(2, len(arr)):
for j in range(len(arr)):
#print arr[j:j+i]
sum_all += sum(arr[j:j+i])
if j+i == len(arr):
break
return sum_all + sum(arr)*2

if __name__ == '__main__':
t = input()
for _ in range(t):
n = input()
arr = map(int, raw_input().strip().split())
print sum_all_sub_arrs(arr) % (10**9+7)

It cant be applied to solve this problem, since if using C++, I can barely pass this problem with runtime nearly reach 5 seconds. (This is Python, so it’s impossible)

After 30 minutes working on papers, I figured out something’s interesting.
Example with input array’s length is odd
Array: 1 2 3 4 5
Sum of all sub-arrays:
1 + 2 + 3 + 4 + 5 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 1 + 2 + 3 + 2 + 3 + 4+ 3 + 4 + 5 + 1 + 2 + 3 + 4 + 2 + 3 + 4 + 5 + 1 + 2 + 3 +4 + 5 = 105
Here’s is the array and the number of times of each element in the equation above:
Array:              1 – 2 – 3 – 4 – 5
Frequency:     5 – 8 – 9 – 8 – 5
Example with input array’s length is even
Array: 1 2 3 4
Sum of all sub-arrays:
1 + 2 + 3 + 4 + 1 + 2 + 2 + 3 + 3 +4 + 1 +2 +3 + 2 + 3 + 4 + 1 +2 + 3 + 4 = 50
Array:           1 – 2 – 3 – 4
Frequency: 4 – 6 – 6 – 4
In general:
+ if length of input array is odd, and n is the length
Frequency: n –  prev+(n-2)  – prev+(n-4) – … – prev+1  – … – prev+(n-4)  – prev+(n-2) – n
+ if length of input array is even, and n is the length
Frequency: n – prev+(n-2) – prev+(n-4) – ….. – prev+(n-4) – prev+(n-2) – n

Code: Python 2.7

def sum_all_sub_arrs(arr):
# input array contains only one element
if len(arr) == 1:
return arr[0]
# init steps
frequency = [0]*len(arr)
dif = len(arr)-2
# because frequency values are symmetric
# example: 4 6 6 4
#          3 4 3
#          etc
# we need to traverse only half first of the input array
# and work out the frequency of each value
for i in range(0, len(arr)//2 + 1 if len(arr) % 2 != 0 else len(arr)//2):
# first frequency = len(arr)
if i == 0:
frequency[i] = len(arr)
# then, each of next element is its previous cell plus difference
# and decrease the difference by 2
else:
frequency[i] += (frequency[i-1] + dif)
dif -= 2
# half left of frequency
for i in range(len(arr)//2+1 if len(arr) % 2 != 0 else len(arr)//2, len(arr)):
offset = len(arr) - i - 1
frequency[i] = frequency[offset]
return sum(x*y for (x,y) in zip(arr, frequency))

if __name__ == '__main__':
t = input()
mod = 10**9 + 7
for _ in range(t):
n = input()
arr = map(int, raw_input().strip().split())
print sum_all_sub_arrs(arr) % mod

Solution took: 94ms

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r