Appearance
Maximum Area of Triangle!
Problem Description
Given a character matrix of size N x M in the form of a string array A of size N where A[i] denotes ith row.
Each character in the matrix consists any one of the following three characters {'r', 'g', 'b'} where 'r' denotes red color similarly 'g' denotes green color and 'b' denotes blue color.
You have to find the area of the largest triangle that has one side parallel to y-axis i.e vertical and the color of all three vertices are different.
NOTE:
- If the area comes out to be a real number than return the ceil of that number.
Problem Constraints
2 <= N, M <= 10^3
A[i][j] = 'r' or A[i][j] = 'g' or A[i][j] = 'b'2 <= N, M <= 10^3
A[i][j] = 'r' or A[i][j] = 'g' or A[i][j] = 'b'Input Format
First and only argument is an string array A of size N denoting the 2D character matrix.First and only argument is an string array A of size N denoting the 2D character matrix.Output Format
Return a single integer denoting the area of the largest triangle that has one side parallel to y-axis i.e vertical and the color of all three vertices are different.
If the area comes out to be a real number than return the ceil of that number.Return a single integer denoting the area of the largest triangle that has one side parallel to y-axis i.e vertical and the color of all three vertices are different.
If the area comes out to be a real number than return the ceil of that number.Example Input
Input 1:
A = ["rrrrr", "rrrrg", "rrrrr", "bbbbb"]
Input 2:
A = ["rrr", "rrr", "rrr", "rrr"]Input 1:
A = ["rrrrr", "rrrrg", "rrrrr", "bbbbb"]
Input 2:
A = ["rrr", "rrr", "rrr", "rrr"]Example Output
Output 1:
10
Output 2:
0Output 1:
10
Output 2:
0Example Explanation
Explanation 1:
The maximum area of triangle is 10.
Triangle coordinates are (0,0) containing r, (1,4) containing g, (3,0) containing b.
Explanation 2:
All cells have same color so no triangle possible so we will return 0Explanation 1:
The maximum area of triangle is 10.
Triangle coordinates are (0,0) containing r, (1,4) containing g, (3,0) containing b.
Explanation 2:
All cells have same color so no triangle possible so we will return 0Solution
swift
import Foundation
class Solution {
func solve(_ A: inout [String]) -> Int {
let N = A.count
let M = A[0].count
var array = [[Character]](repeating:[Character](repeating:"r",count:M),count:N)
for (i,str) in A.enumerated() {
for (j,c) in str.enumerated(){
array[i][j] = c
}
}
var base = [[Int]](repeating:[0,0,0],count:M)
var exist = [[Int]](repeating:[0,0,0],count:M)
for i in 0..<M {
var r = [Int]()
var g = [Int]()
var b = [Int]()
for j in 0..<N{
let c = array[j][i]
if c == "r" {
r.append(j)
} else if c == "g" {
g.append(j)
} else {
b.append(j)
}
}
var rg = 0
var gb = 0
var rb = 0
if r.count > 0 && g.count > 0 {
rg = max(r.max()! - g.min()!,g.max()! - r.min()!) + 1
}
if g.count > 0 && b.count > 0 {
gb = max(g.max()! - b.min()!,b.max()! - g.min()!) + 1
}
if r.count > 0 && b.count > 0 {
rb = max(r.max()! - b.min()!,b.max()! - r.min()!) + 1
}
base[i][0] = rg
exist[i][0] = b.count
base[i][1] = gb
exist[i][1] = r.count
base[i][2] = rb
exist[i][2] = g.count
}
var result = 0
for i in 0..<M {
for k in 0..<3 {
let b = base[i][k]
if b == 0 {
continue
}
let w = max(M-1-i,i)
for j in (1...w).reversed() {
var index = i + j
if index < M {
if exist[index][k] > 0 {
let v = b * (j+1)
if v > result {
result = v
}
break
}
}
index = i - j
if index >= 0 {
if exist[index][k] > 0 {
let v = b * (j+1)
if v > result {
result = v
}
break
}
}
}
}
}
return (result+1)/2
}
}import Foundation
class Solution {
func solve(_ A: inout [String]) -> Int {
let N = A.count
let M = A[0].count
var array = [[Character]](repeating:[Character](repeating:"r",count:M),count:N)
for (i,str) in A.enumerated() {
for (j,c) in str.enumerated(){
array[i][j] = c
}
}
var base = [[Int]](repeating:[0,0,0],count:M)
var exist = [[Int]](repeating:[0,0,0],count:M)
for i in 0..<M {
var r = [Int]()
var g = [Int]()
var b = [Int]()
for j in 0..<N{
let c = array[j][i]
if c == "r" {
r.append(j)
} else if c == "g" {
g.append(j)
} else {
b.append(j)
}
}
var rg = 0
var gb = 0
var rb = 0
if r.count > 0 && g.count > 0 {
rg = max(r.max()! - g.min()!,g.max()! - r.min()!) + 1
}
if g.count > 0 && b.count > 0 {
gb = max(g.max()! - b.min()!,b.max()! - g.min()!) + 1
}
if r.count > 0 && b.count > 0 {
rb = max(r.max()! - b.min()!,b.max()! - r.min()!) + 1
}
base[i][0] = rg
exist[i][0] = b.count
base[i][1] = gb
exist[i][1] = r.count
base[i][2] = rb
exist[i][2] = g.count
}
var result = 0
for i in 0..<M {
for k in 0..<3 {
let b = base[i][k]
if b == 0 {
continue
}
let w = max(M-1-i,i)
for j in (1...w).reversed() {
var index = i + j
if index < M {
if exist[index][k] > 0 {
let v = b * (j+1)
if v > result {
result = v
}
break
}
}
index = i - j
if index >= 0 {
if exist[index][k] > 0 {
let v = b * (j+1)
if v > result {
result = v
}
break
}
}
}
}
}
return (result+1)/2
}
}