Given the coordinates of 5 2-dimensional points, check if they form a closed T shape. Print ‘Yes’ if they form T shape and ‘No’ otherwise. Note: Coordinates should be distinct and integers.
There are 4-types of T shaped formations possible according to the given conditions:
Examples:
Input: [[7, 5], [8, 5], [6, 5], [7, 7], [7, 6]] Output: Yes Input: [[0, 0], [1, 0], [2, 0], [1, -1], [1, -2]] Output: Yes
Approach:
- Consider the first point in the given list as the center (x, y) (i.e intersection of the two lines that form a T-shape).
- Then check if all the points which are needed to form a T-shape of which (x, y) are the center are present in the list of given points or not.
- Check this for all 4 possible patterns of T-shape.
Below is the implementation of the above approach:
C++
// C++ code to check if given 5// 2-D points form T-shape or not#include <bits/stdc++.h>using namespace std;// This function checks if the points// form T-shape pointing upbool isUpDirected(map<pair<int, int>, int> point, int x, int y){ return (point[{ x - 1, y }] and point[{ x, y }] and point[{ x + 1, y }] and point[{ x, y - 1 }] and point[{ x, y - 2 }]);}// This function checks if the points// form T-shape pointing downbool isDownDirected(map<pair<int, int>, int> point, int x, int y){ return (point[{ x - 1, y }] and point[{ x, y }] and point[{ x + 1, y }] and point[{ x, y + 1 }] and point[{ x, y + 2 }]);}// This function checks if the points// form T-shape pointing leftbool isLeftDirected(map<pair<int, int>, int> point, int x, int y){ return (point[{ x, y + 1 }] and point[{ x, y }] and point[{ x, y - 1 }] and point[{ x + 1, y }] and point[{ x + 2, y }]);}// This function checks if the points// form T-shape pointing rightbool isRightDirected(map<pair<int, int>, int> point, int x, int y){ return (point[{ x, y + 1 }] and point[{ x, y }] and point[{ x, y - 1 }] and point[{ x - 1, y }] and point[{ x - 2, y }]);}// This function checks if given points// form a T-shape or notstring solve(int grid[][2], int n){ // Initialize the dictionary with False value map<pair<int, int>, int> point; bool flag = false; for (int i = 0; i < n; i++) { // Assign True value to the points which // are present in the given list point[{ grid[i][0], grid[i][1] }] = true; } for (int i = 0; i < n; i++) { // Check if the given points form any of the // 4 possible T-shaped formations if (isUpDirected(point, grid[i][0], grid[i][1]) or isDownDirected(point, grid[i][0], grid[i][1]) or isLeftDirected(point, grid[i][0], grid[i][1]) or isRightDirected(point, grid[i][0], grid[i][1])) { flag = true; break; } } if (flag) return "Yes"; else return "No";}int main(){ int grid1[][2] = { { 7, 5 }, { 8, 5 }, { 6, 5 }, { 7, 7 }, { 7, 6 } }; int n1 = 5; cout << solve(grid1, n1) << endl; int grid2[][2] = { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 1, -1 }, { 1, -2 } }; int n2 = 5; cout << solve(grid2, n2) << endl;}// This code is contributed by phasing17 |
Python3
# Python3 code to check if given 5# 2-D points form T-shape or not# Import the function to initialize the# dictionary with a specific valuefrom collections import defaultdict# This function checks if the points# form T-shape pointing updef isUpDirected(point, x, y): return (point[(x-1, y)] and point[(x, y)] and point[(x + 1, y)] and point[(x, y-1)] and point[(x, y-2)])# This function checks if the points# form T-shape pointing downdef isDownDirected(point, x, y): return (point[(x-1, y)] and point[(x, y)] and point[(x + 1, y)] and point[(x, y + 1)] and point[(x, y + 2)])# This function checks if the points# form T-shape pointing leftdef isLeftDirected(point, x, y): return (point[(x, y + 1)] and point[(x, y)] and point[(x, y-1)] and point[(x + 1, y)] and point[(x + 2, y)])# This function checks if the points# form T-shape pointing rightdef isRightDirected(point, x, y): return (point[(x, y + 1)] and point[(x, y)] and point[(x, y-1)] and point[(x-1, y)] and point[(x-2, y)])# This function checks if given points# form a T-shape or notdef solve(grid): # Initialize the dictionary with False value point = defaultdict(lambda: False) flag = False for i in range(len(grid)): # Assign True value to the points which # are present in the given list point[(grid[i][0], grid[i][1])] = True for i in range(len(grid)): # Check if the given points form any of the # 4 possible T-shaped formations if isUpDirected(point, grid[i][0], grid[i][1]) or isDownDirected(point, grid[i][0], grid[i][1]) or isLeftDirected(point, grid[i][0], grid[i][1]) or isRightDirected(point, grid[i][0], grid[i][1]): flag = True break if flag == True: return 'Yes' else: return 'No'print(solve([[7, 5], [8, 5], [6, 5], [7, 7], [7, 6]]))print(solve([[0, 0], [1, 0], [2, 0], [1, -1], [1, -2]])) |
C#
// C# code to check if given 5// 2-D points form T-shape or notusing System;using System.Collections.Generic;class GFG{ // This function checks if the points // form T-shape pointing up static bool isUpDirected(Dictionary<string, int> point, int x, int y) { return (point.ContainsKey(string.Join(",", new [] {x - 1, y })) && point.ContainsKey(string.Join(",", new[] { x, y })) && point.ContainsKey(string.Join(",", new[] { x + 1, y })) && point.ContainsKey(string.Join(",", new[] { x, y - 1 })) && point.ContainsKey(string.Join(",", new[] { x, y - 2 }))); } // This function checks if the points // form T-shape pointing down static bool isDownDirected(Dictionary<string, int> point, int x, int y) { return (point.ContainsKey(string.Join(",", new[] { x - 1, y })) && point.ContainsKey(string.Join(",", new[] { x, y })) && point.ContainsKey(string.Join(",", new[] { x + 1, y })) && point.ContainsKey(string.Join(",", new[] { x, y + 1 })) && point.ContainsKey(string.Join(",", new[] { x, y + 2 }))); } // This function checks if the points // form T-shape pointing left static bool isLeftDirected(Dictionary<string, int> point, int x, int y) { return (point.ContainsKey(string.Join(",", new[] { x, y + 1 })) && point.ContainsKey(string.Join(",", new[] { x, y })) && point.ContainsKey(string.Join(",", new[] { x, y - 1 })) && point.ContainsKey(string.Join(",", new[] { x + 1, y })) && point.ContainsKey(string.Join(",", new[] { x + 2, y }))); } // This function checks if the points // form T-shape pointing right static bool isRightDirected(Dictionary<string, int> point, int x, int y) { return (point.ContainsKey(string.Join(",", new[] { x, y + 1 })) && point.ContainsKey(string.Join(",", new[] { x, y })) && point.ContainsKey(string.Join(",", new[] { x, y - 1 })) && point.ContainsKey(string.Join(",", new[] { x - 1, y })) && point.ContainsKey(string.Join(",", new[] { x - 2, y }))); } // This function checks if given points // form a T-shape or not static string solve(int[, ] grid, int n) { // Initialize the dictionary with False value Dictionary<string, int> point = new Dictionary<string, int>(); bool flag = false; for (int i = 0; i < n; i++) { // Assign True value to the points which // are present in the given list point[string.Join(",", new[] { grid[i, 0], grid[i, 1] })] = 1; } for (int i = 0; i < n; i++) { // Check if the given points form any of the // 4 possible T-shaped formations if (isUpDirected(point, grid[i, 0], grid[i, 1]) || isDownDirected(point, grid[i, 0], grid[i, 1]) || isLeftDirected(point, grid[i, 0], grid[i, 1]) || isRightDirected(point, grid[i, 0], grid[i, 1])) { flag = true; break; } } if (flag) return "Yes"; else return "No"; } public static void Main(string[] args) { int[, ] grid1 = { { 7, 5 }, { 8, 5 }, { 6, 5 }, { 7, 7 }, { 7, 6 } }; int n1 = 5; Console.WriteLine(solve(grid1, n1)); int[, ] grid2 = { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 1, -1 }, { 1, -2 } }; int n2 = 5; Console.WriteLine(solve(grid2, n2)); }}// This code is contributed by phasing17 |
Javascript
// JavaScript code to check if given 5// 2-D points form T-shape or not// Import the function to initialize the// dictionary with a specific value// This function checks if the points// form T-shape pointing upfunction isUpDirected(point, x, y){ return (point.has([x-1, y].join()) && point.has([x, y].join()) && point.has([x+1, y].join()) && point.has([x, y-1].join()) && point.has([x, y-2].join()));}// This function checks if the points// form T-shape pointing downfunction isDownDirected(point, x, y){ return (point.has([x-1, y].join()) && point.has([x, y].join()) && point.has([x+1, y].join()) && point.has([x, y+1].join()) && point.has([x, y+2].join())); }// This function checks if the points// form T-shape pointing leftfunction isLeftDirected(point, x, y){ return (point.has([x, y+1].join()) && point.has([x, y].join()) && point.has([x, y-1].join()) && point.has([x+1, y].join()) && point.has([x+2, y].join()));}// This function checks if the points// form T-shape pointing rightfunction isRightDirected(point, x, y){ return (point.has([x, y+1].join()) && point.has([x, y].join()) && point.has([x, y-1].join()) && point.has([x+1, y].join()) && point.has([x+2, y].join()));}// This function checks if given points// form a T-shape or notfunction solve(grid){ // Initialize the dictionary with False value let point = new Map(); let flag = false; for(let i = 0; i < grid.length; i++){ // Assign True value to the points which // are present in the given list point.set([grid[i][0], grid[i][1]].join(), true); } for(let i = 0; i < grid.length; i++){ // Check if the given points form any of the // 4 possible T-shaped formations if(isUpDirected(point, grid[i][0], grid[i][1]) || isDownDirected(point, grid[i][0], grid[i][1]) || isLeftDirected(point, grid[i][0], grid[i][1]) || isRightDirected(point, grid[i][0], grid[i][1])){ flag = true; break; } } if (flag == true){ return 'Yes'; } else{ return 'No'; } }// Driver code console.log(solve([[7, 5], [8, 5], [6, 5], [7, 7], [7, 6]]));console.log(solve([[0, 0], [1, 0], [2, 0], [1, -1], [1, -2]]));// The code is contributed by Nidhi goel |
Java
// Java code to check if given 5// 2-D points form T-shape or notimport java.util.*;class GFG { static String Join(String d, int[] arr) { String res = String.valueOf(arr[0]) + d + String.valueOf(arr[1]); return res; } // This function checks if the points // form T-shape pointing up static boolean isUpDirected(HashMap<String, Integer> point, int x, int y) { return (point.containsKey( Join(",", new int[] { x - 1, y })) && point.containsKey( Join(",", new int[] { x, y })) && point.containsKey( Join(",", new int[] { x + 1, y })) && point.containsKey( Join(",", new int[] { x, y - 1 })) && point.containsKey( Join(",", new int[] { x, y - 2 }))); } // This function checks if the points // form T-shape pointing down static boolean isDownDirected(HashMap<String, Integer> point, int x, int y) { return (point.containsKey( Join(",", new int[] { x - 1, y })) && point.containsKey( Join(",", new int[] { x, y })) && point.containsKey( Join(",", new int[] { x + 1, y })) && point.containsKey( Join(",", new int[] { x, y + 1 })) && point.containsKey( Join(",", new int[] { x, y + 2 }))); } // This function checks if the points // form T-shape pointing left static boolean isLeftDirected(HashMap<String, Integer> point, int x, int y) { return (point.containsKey( Join(",", new int[] { x, y + 1 })) && point.containsKey( Join(",", new int[] { x, y })) && point.containsKey( Join(",", new int[] { x, y - 1 })) && point.containsKey( Join(",", new int[] { x + 1, y })) && point.containsKey( Join(",", new int[] { x + 2, y }))); } // This function checks if the points // form T-shape pointing right static boolean isRightDirected(HashMap<String, Integer> point, int x, int y) { return (point.containsKey( Join(",", new int[] { x, y + 1 })) && point.containsKey( Join(",", new int[] { x, y })) && point.containsKey( Join(",", new int[] { x, y - 1 })) && point.containsKey( Join(",", new int[] { x - 1, y })) && point.containsKey( Join(",", new int[] { x - 2, y }))); } // This function checks if given points // form a T-shape or not static String solve(int[][] grid, int n) { // Initialize the HashMap with False value HashMap<String, Integer> point = new HashMap<String, Integer>(); boolean flag = false; for (int i = 0; i < n; i++) { // Assign True value to the points which // are present in the given list point.put(Join(",", new int[] { grid[i][0], grid[i][1] }), 1); } for (int i = 0; i < n; i++) { // Check if the given points form any of the // 4 possible T-shaped formations if (isUpDirected(point, grid[i][0], grid[i][1]) || isDownDirected(point, grid[i][0], grid[i][1]) || isLeftDirected(point, grid[i][0], grid[i][1]) || isRightDirected(point, grid[i][0], grid[i][1])) { flag = true; break; } } if (flag) return "Yes"; else return "No"; } public static void main(String[] args) { int[][] grid1 = { { 7, 5 }, { 8, 5 }, { 6, 5 }, { 7, 7 }, { 7, 6 } }; int n1 = 5; System.out.println(solve(grid1, n1)); int[][] grid2 = { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 1, -1 }, { 1, -2 } }; int n2 = 5; System.out.println(solve(grid2, n2)); }}// This code is contributed by phasing17 |
Output:
Yes Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
