Browser tab content: Problem List
0
Debugging...
Run
Submit
00:00:00
Description
Editorial
Editorial
Solutions
Solutions
Submissions
Submissions
Debugger
Debugger
Code
Note
Note
Testcase
Testcase
Test Result
317. Shortest Distance from All Buildings
Hard
Topics
Companies

You are given an m x n grid grid of values 0, 1, or 2, where:

each 0 marks an empty land that you can pass by freely,
each 1 marks a building that you cannot pass through, and
each 2 marks an obstacle that you cannot pass through.

You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.

Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

 

Example 1:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal.
So return 7.


Example 2:

Input: grid = [[1,0]]
Output: 1


Example 3:

Input: grid = [[1]]
Output: -1


 

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0, 1, or 2.
There will be at least one building in the grid.
Seen this question in a real interview before?
1/5
Yes
No
Accepted
186.7K
Submissions
428.5K
Acceptance Rate
43.6%
Topics
Array
Breadth-First Search
Matrix
Companies
0 - 3 months
Meta
4
DoorDash
3
Apple
2
0 - 6 months
Google
3
Amazon
2
Zenefits
2
6 months ago
Snap
3
ByteDance
2
TikTok
2
Similar Questions
Walls and Gates
Medium
Best Meeting Point
Hard
As Far from Land as Possible
Medium
Discussion (30)
Choose a type
Preview
Comment
💡 Discussion Rules

1. Please don't post any solutions in this discussion.

2. The problem discussion is for asking questions about the problem or for sharing tips - anything except for solutions.

3. If you'd like to share your solution for feedback and ideas, please head to the solutions tab and post it there.

Sort by:Best
No comments yet.
1
2
3
Copyright ©️ 2024 LeetCode All rights reserved
1.9K
30
19 Online
Java
Auto
1
2
3
4
5
class Solution {
    public int shortestDistance(int[][] grid) {
        
    }
}
Saved
Ln 4, Col 6
Wrong Answer
Runtime: 0 ms
Case 1
Case 2
Case 3
Input
grid =
[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output
-1
Expected
7
Contribute a testcase
Input
1
2
3
[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
[[1,0]]
[[1]]
Output
1
2
3
-1
1
-1
Expected
1
2
3
7
1
-1

Shortest Word Distance III - LeetCode

Problem List
Tag
243. Shortest Word Distance

Easy

244. Shortest Word Distance II

Med.

245. Shortest Word Distance III

Med.

246. Strobogrammatic Number

Easy

247. Strobogrammatic Number II

Med.

248. Strobogrammatic Number III

Hard

249. Group Shifted Strings

Med.

250. Count Univalue Subtrees

Med.

251. Flatten 2D Vector

Med.

252. Meeting Rooms

Easy

253. Meeting Rooms II

Med.

254. Factor Combinations

Med.

255. Verify Preorder Sequence in Binary Search Tree

Med.

256. Paint House

Med.

257. Binary Tree Paths

Easy

258. Add Digits

Easy

259. 3Sum Smaller

Med.

260. Single Number III

Med.

261. Graph Valid Tree

Med.

262. Trips and Users

Hard

263. Ugly Number

Easy

264. Ugly Number II

Med.

265. Paint House II

Hard

266. Palindrome Permutation

Easy

267. Palindrome Permutation II

Med.

268. Missing Number

Easy

269. Alien Dictionary

Hard

270. Closest Binary Search Tree Value

Easy

271. Encode and Decode Strings

Med.

272. Closest Binary Search Tree Value II

Hard

273. Integer to English Words

Hard

274. H-Index

Med.

275. H-Index II

Med.

276. Paint Fence

Med.

277. Find the Celebrity

Med.

278. First Bad Version

Easy

279. Perfect Squares

Med.

280. Wiggle Sort

Med.

281. Zigzag Iterator

Med.

282. Expression Add Operators

Hard

283. Move Zeroes

Easy

284. Peeking Iterator

Med.

285. Inorder Successor in BST

Med.

286. Walls and Gates

Med.

287. Find the Duplicate Number

Med.

288. Unique Word Abbreviation

Med.

289. Game of Life

Med.

290. Word Pattern

Easy

291. Word Pattern II

Med.

292. Nim Game

Easy

293. Flip Game

Easy

294. Flip Game II

Med.

295. Find Median from Data Stream

Hard

296. Best Meeting Point

Hard

297. Serialize and Deserialize Binary Tree

Hard

298. Binary Tree Longest Consecutive Sequence

Med.

299. Bulls and Cows

Med.

300. Longest Increasing Subsequence

Med.

301. Remove Invalid Parentheses

Hard

302. Smallest Rectangle Enclosing Black Pixels

Hard

303. Range Sum Query - Immutable

Easy

304. Range Sum Query 2D - Immutable

Med.

305. Number of Islands II

Hard

306. Additive Number

Med.

307. Range Sum Query - Mutable

Med.

308. Range Sum Query 2D - Mutable

Hard

309. Best Time to Buy and Sell Stock with Cooldown

Med.

310. Minimum Height Trees

Med.

311. Sparse Matrix Multiplication

Med.

312. Burst Balloons

Hard

313. Super Ugly Number

Med.

314. Binary Tree Vertical Order Traversal

Med.

315. Count of Smaller Numbers After Self

Hard

316. Remove Duplicate Letters

Med.

317. Shortest Distance from All Buildings

Hard

318. Maximum Product of Word Lengths

Med.

319. Bulb Switcher

Med.

320. Generalized Abbreviation

Med.

321. Create Maximum Number

Hard

322. Coin Change

Med.

323. Number of Connected Components in an Undirected Graph

Med.

324. Wiggle Sort II

Med.

325. Maximum Size Subarray Sum Equals k

Med.

326. Power of Three

Easy

327. Count of Range Sum

Hard

328. Odd Even Linked List

Med.

329. Longest Increasing Path in a Matrix

Hard

330. Patching Array

Hard

331. Verify Preorder Serialization of a Binary Tree

Med.

332. Reconstruct Itinerary

Hard

333. Largest BST Subtree

Med.

334. Increasing Triplet Subsequence

Med.

335. Self Crossing

Hard

336. Palindrome Pairs

Hard

337. House Robber III

Med.

338. Counting Bits

Easy

339. Nested List Weight Sum

Med.

340. Longest Substring with At Most K Distinct Characters

Med.

341. Flatten Nested List Iterator

Med.

342. Power of Four

Easy

343. Integer Break

Med.

344. Reverse String

Easy

345. Reverse Vowels of a String

Easy

346. Moving Average from Data Stream

Easy

347. Top K Frequent Elements

Med.

348. Design Tic-Tac-Toe

Med.

349. Intersection of Two Arrays

Easy

350. Intersection of Two Arrays II

Easy

351. Android Unlock Patterns

Med.

352. Data Stream as Disjoint Intervals

Hard

353. Design Snake Game

Med.

354. Russian Doll Envelopes

Hard

355. Design Twitter

Med.

356. Line Reflection

Med.

357. Count Numbers with Unique Digits

Med.

358. Rearrange String k Distance Apart

Hard

359. Logger Rate Limiter

Easy

360. Sort Transformed Array

Med.

361. Bomb Enemy

Med.

362. Design Hit Counter

Med.

363. Max Sum of Rectangle No Larger Than K

Hard

364. Nested List Weight Sum II

Med.

365. Water and Jug Problem

Med.

366. Find Leaves of Binary Tree

Med.

367. Valid Perfect Square

Easy

368. Largest Divisible Subset

Med.

369. Plus One Linked List

Med.

370. Range Addition

Med.

371. Sum of Two Integers

Med.

372. Super Pow

Med.

373. Find K Pairs with Smallest Sums

Med.

374. Guess Number Higher or Lower

Easy

375. Guess Number Higher or Lower II

Med.

376. Wiggle Subsequence

Med.

377. Combination Sum IV

Med.

378. Kth Smallest Element in a Sorted Matrix

Med.

379. Design Phone Directory

Med.

380. Insert Delete GetRandom O(1)

Med.

381. Insert Delete GetRandom O(1) - Duplicates allowed

Hard

382. Linked List Random Node

Med.

383. Ransom Note

Easy

384. Shuffle an Array

Med.

385. Mini Parser

Med.

386. Lexicographical Numbers

Med.

387. First Unique Character in a String

Easy

388. Longest Absolute File Path

Med.

389. Find the Difference

Easy

390. Elimination Game

Med.

391. Perfect Rectangle

Hard

392. Is Subsequence

Easy

Remove distracting text, extract the programming question, provide simple, common, and optimized Java solution for it.